Lots of people (including myself) have had similar problems. It seems to be related to PCs failing to connect properly with their ISP's domain name server. I've no idea why this happens but I do know that the following always seems to fix it:
First, find out the logical addresses of the primary and secondary domain name servers used by your ISP. (If you're not 'technically minded', don't panic. That just means that you need a couple of sets of numbers, such as 194.72.6.57). The information will be on the support pages of your ISP's website but, if you're with one of the big UK ISPs, you can probably find the information quicker here:
http://www.idl.uk.com/email/isp_settings.htm
or here:
http://www.kitz.co.uk/isp/dns.htm
Now go to your dial-up networking settings and right-click on the icon for your dial-up connection. Select 'Properties'. Then click the 'Networking' tab and the 'TCP/IP Settings' button.
Click to place a dot alongside 'Specify name server addresses'. Fill in the relevant numbers for 'Primary DNS' and 'Secondary DNS'. Click 'OK' twice. Job done and (hopefully) problem fixed.
Chris
(PS: As an alternative to using your ISP's domain name servers, you can use the settings for 'OpenDNS'. They're given at the foot of the second link I've given above. Some people, including myself, find that these give a slight improvement in download times)