I didn't read all of the responses, so maybe someone has already mentioned this. I had a similar problem when I installed a blackberry device. Try this: Rclick Outlook icon/properties. make sure microsoft exch server is highlighted then click the properties button. click the 'advanced tab'. in the "logon network security" box, select "NT Password Authentication". I've used this fix quite often.
good luck