I had the same problem. The issue is that Windows handles the proxy authentication separately from it's proxy settings, and when the proxy server asks for the username and password, Calibre has no way of recognising the request or getting the username and password from the user.
My workaround was to tell Windows my username and password so that Calibre does not need to worry about it. Unfortunately, setting the proxy under Internet Options in Windows does not let you specify a username and password within the proxy. The solution was to set a new environment variable.
- Right click on My Computer and select Properties
- In Windows 7, choose Advanced System Settings on the left. On XP, select the Advanced tab.
- Click on the Environment Variables button
- Under user variables, click New
- Enter the variable name as http_proxy and the variable value as the following:
Or if your proxy needs a domain name to be specified:
Obviously replacing the  with whatever is supposed to be there.
- Click OK on all the open dialogs.
After doing this, Calibre was able to connect to the internet and fetch metadata, as well as several other internet related tasks which it could not do before. (Using Calibre 0.8.0 on Windows 7)