I had the same problem with T-Online in southern Germany recently. No logical reason - I hadn't changed any of my settings. I tried a system restore to a time when I knew it worked - that didn't fix things. Every time it would hang on the 'proxy settings' stage of the attempted log-in, then 'server could not be found' came up.
It then fixed itself the next morning. Baffling.
One thing you could check though - go to Wireless Network Properties, click on the 'Wireless Networks' tab and highlight the name of the relevant public access network in the list displayed. Then click 'properties' and confirm under 'association' that 'Network Autherntication' is Open and 'Data encryption' is 'disabled'.