Unable To Connect To Microsoft Office Online?

In our office, running both Office 2007 and 2010, when trying to create a new document from a template (ex.: business cards or letters), I get a message that says "Unable to connect to Microsoft Office Online" with 2 options: "Try again" and "Troubleshoot your internet connection" (Office 2010 has a third option: "Tell us what you are looking for"). The product is activated on both and I am able to connect directly via a browser to the template site here:http://office.microsoft.com/en-au/templates/?CTT=97 . I can ping microsoft.com and have no other connectivity issues, and our network firewall and the local firewall are not blocking anything Office-related as far as I know. In fact, on one computer, I logged in as the local administrator and was able to connect doing the same thing, then logged back in as a network user AND the network administrator and both failed once again. What would cause this between accounts, and FYI, this method did NOT work on 2 other computers (logging in as the local admin). This occurs on both Office 2007 and 2010 products (2010 is running on Windows 7, 2007 is running on Windows XP).Also, I tried using the computer (under the local admin account) on our public network (like a home network connected by cable modem, using DHCP) and it worked fine also, if that makes any difference.