Does the 2nd login work? We had this same issue on our Exchange 2007 when some services were not running correctly on the mailbox server. Check the services make sure they are all running. Run the best practices analyzer on the boxes to see if anything is uncovered.
You do not say if this is a front end/back end scenario. If it is, then you need to set the authentication on the front end to basic, and then set the back end owa authentication to windows pass through authentication. You should also have an ssl cert on the front end. This should resolve the double prompt issue.
Here is a good article to help you decide the best scenario for authentication.