It can comes from many things, but here are the clues I know:
-Try on different computers with different users.
-When you get this error, go to control panel/courrier/ then remove the outlook profile before trying again.
-The other source of this problem is the GAL itself.
The RUS set up Exchange users's properties in AD. One of them is very important, showInAddressBook.
If this is a new user, try to force a rebuild of the RUS and offline addressbook and check eventlog for errors.
If the RUS or offline book is concerned, you can reset the Exchange system folder (take care!), KB 822444
From Microsoft KB:
How the Recipient Update Service Populates Address Lists
Troubleshooting the Recipient Update Service in Exchange Server 2003 and Exchange 2000 Server
Troubleshooting Check Name errors