I have a new Exchange 2007 server, and recently one user cannot connect to his mailbox through Outlook 2003 on any machine. He can connect with OWA, and his assistant can see his inbox in her outlook... But he cannot connect himself. On machines that he used to connect with, he gets error 0x8004011D. On the new machine we tried, we get an error "Unable to open your default e-mail folders...." The problem seems to be isolated to this one user.

Is this user using local cache mode? Try deleting the entire Outlook profile (and OST file) and recreate it. Also, try mounting and then dismounting the mailbox database where this user's mailboxis located (I know that is weird, but I have seen that fix some problems)