In which branch of your directory server are you adding your users?
If you are adding users through the console the first time add them in the correct People branch, the one that has Messaging Server related attributes. If you are adding users under the incorrect branch of your directory tree when you try to log in Messanger Express it won't find the users although you can see them in the Directory Server.
Hope this could help you.