sunspark,
I ran into this with Hotdesk ACD agents. They could log in no problem in the beginning, but as soon as they changed their password on their mailbox they could no longer log in with the passcode we gave them. If they used their voicemail passcode as their Hotdesk passcode everything worked as expected.
If you want to fix the issue you have to go into the MCD and blank out the application data and then go back and put in the hotdesk passcode that you want. I found it easier to just let the users know to use their mailbox passcode.
Thanks,
TE