License Problem

I have Exchange 5.5 running on Win 2k server. I have issued the proper number of licenses, both on the Win2k Server and the Exchange 5.5 properties tabs. Why when I have a new user log in, do I recieve an error about not enough licenses to log into their Exchange Mailbox? Any Suggestions, I am in a bind!