Outlook can not connect to Mailbox

[Overdoos]

Hi,
I'm running an Exchange mailserver with outlook clients on a win NT system (servers and workstations).
It all runs (pretty) fine, but one of my users keeps getting in trouble with his mailbox.
I've already tried to delete his profile and create a new one, I've deleted his user-account and recreated it, I've re-installed Outlook... nothing workes.
Opening an other mailbox on his PC using another profiles does not cause this error, nor do I get this error if I access his mailbox using the administrator account (not even on his workstation).
Has anybody got any other solutions?

 

[uriel717]

What exactly is the message? When you added the new profile in the Mail control panel, were you able to 'Check Name' on the Exchange server?