We installed a new front end server and had the same issue. There are several things I learned.
First, you did not say if you were using a front end server or if you only have one mail server, nor did you mention which exchange version you are using.
If OWA is being served up via a front end server, and it is an exchange 2003 server, you have to change the peremissions on that server via exchange system manager.
What you need to know is that a front end server in exchange does not allow windows authentication (commonly known as pass through authentication). You have to set the front end to basic authentication. Then set the back end server to windows authenticaion and basic authentication.
http://technet.microsoft.com/en-us/library/eb063679-51a8-4cc0-9773-e5f1eb6edf31.aspx
If you are running exchange 2000 the change has to be made in IIS.
Exchange 2003 System manager settings will overwrite IIS settings after 15 minutes, which is why you have to make the changes for exchange 2003 in the system manager, not IIS. Go to the server name, protocols, HTTP, Exchange Virtual Server and right-click the Exchange folder, go to properties then the access tab and click the "authentication" button. Again, front end servers need to have basic ONLY checked. Back end servers need basic AND windows authentication checked.
Other issues may be your DNS host name entries or cname alias entries, but someone else can tackle that part if they wish.