Ok, here is the situation:
Created new mailbox on Exchange server. After mailbox has been created, I navigate to OWA to login as that user and receive the following error:
The item you tried to access no longer exists.
The item wasn't found. You or a delegate might have moved or deleted it using another computer or a mobile phone.
I created another user to see if I could replicate the issue and it does the same for all new user accounts.
If I login to a Windows 7 Pro system and try to configure Outlook over RPC I get:
"The name cannot be matched to a name in the address list."
All existing accounts are not having issues, just new accounts that are created.