So I just happened to be in the office when one of our new staff tried to log in to her email account for the first time. SOP is to set up all new accounts with a default password and check the "Must change password" option so they need to input a new password at their first login.
The new user logged in with the defaults and was prompted to enter a new password. At that time, she mistyped one of them and was prompted to try again ("new passwords must match"). She carefully retyped and submitted- this time, a very curious error came up about an invalid username and password. No matter what we tried to type in for the new password, we would always get that error. I had her close the browser and try again with the same results (minus the mistype of the password).
Thinking it could be an IE weirdness, I had her switch to FF3 and try again. Same sequence of events. At that point I logged in to the Admin console and pulled up her account which showed her as "Never logged in" (which, technically, I guess she never had), so I unchecked the "Must change password" option, and had her try again. With the defaults unedited except for that one change, she was able to log in, go to her preferences and change her password from there with no problem.

I haven't had any other reports from the new users, so I don't know if anyone else has had the same difficulty. I'm stumped.