Point out to them they are breaking that contract by not providing a decent standard of service, though its tiscali so dont hold your breath.
If it is a problem there end, which is seems like as they are acknowledging it, all you can do is wait. Find out on some forums more related to connectivity such as
http://forums.speedguide.net/index.php? if other users of tiscali in the same area are actually having problems, for a good indication of if its your settings at fault.
If tiscali are having problems with there dns servers it shouldnt exactly take them long to fix it.