I would download the Windows 2003 Support Tools and run a
netdiag /v
and see what comes up and report that back. It sounds like some configuration setting you might have ... perhaps static DNS servers?
Were there any other problems you were experiencing with other servers / services?