Outlook/Exchange issue

We’re using Microsoft Small Business Server 2003 with Exchange. I recently added a new OU and added a new user to that OU and created a mailbox for him which is enabled. I then added his computer to the domain, then added Outlook 2002 and tried to configure an MS Exchange account for him but I type the name of the server then his name and click on “Check Name” and get the following message:

THE ACTION COULD NOT BE COMPLETED. THE NAME COULD NOT BE MATCHED TO A NAME IN THE ADDRESS LIST.

I’ve checked and his mailbox shows up in the mailbox store. I am currently at a loss and would appreciate any help.