hmmm indeed.
The most likely explanation is DNS issues
>> I've just discovered that I can connect with Frostwire and search for files without a problem
Im not familiar with frostwire.. but it appears to be a p2p search tool. If this is the case then it will be searching on the IP address of who is connected to their servers.
So yet again no problems with connections via the IP address, so its not the actual broadband connection
Try using OpenDNS
https://www.opendns.com/smb/start