I finally got it working but it wasn't quite how the Gem FAQ stipulates, so I thought I would share it.
The Simple Solution
Execute the following command from the command prompt.
Your gem commands should now work fine.
The Complex Solution
- Get hold of the 'NTLM authorization Proxy Server' currently on source forge as ntlmaps.
- Configure it so it known your login to the real proxy server. (you edit the server.cfg, but see gems faq page for details)
- Set HTTP_PROXY as above but pointing to your new proxy server
- If it still doesn't work, try passing your login credentials to the new proxy server.
Note: I tried the gem commands using the -p switch but most commands don't work properly. I was getting "ERROR: While executing gem ... (Errno::EBADF)"
Using the environment variable HTTP_PROXY instead fixed this.