Sounds to me the server properties are messed up. Check the Outlook icon on your desktop. Highlight and right-click > Properties > select the server in the window (should say something about Exchange server) > Properties button - you want to check the server is correctly identified in the following window as well as the user name.

Of course I could be completely wrong since I haven't used Outlook in a while so I'm kinda going by memory.

You are on the right track that creating a new profile is working - it has the right settings. If nothing else - just delete the first profile that is goofed adn you should be alright.