Same problem, CB4 area.
It seems like their DNS servers (at least, and probably lots of other things) are broken - try the same lookup 10-20 times in a row and sometimes you get the IP back (
www.ntlworld.com for example). You'll find that you can ping anything you can actually get a lookup for just fine, no packet loss.
I'm going to phone them now.