fumakiller, what's your proxy server? Is it linux-based squid or MS ISA Server?
ISA Server by default denies access for SYSTEM account that is used for auto-updates. In this case, you can set NTLM authentication and fill credentials with username in form DOMAIN\user.