Actually, it came back on Sunday. The new password I set started working, and I could re-establish my Blackberry account.
Today I got an email from Google in response to my problem:
We’re sorry to hear you’ve had trouble accessing your mail. Please followthe steps below to resolve the problem:
1. Disable all mail clients you’re using to read mail. (If you use one atwork and one at home, please disable both.)
2. From the computer on which your logins are failing, visithttps://www.google.com/a/[your domain].com/UnlockCaptcha. Be sure to fillin your domain name in the URL.
3. Enter your email username and password, and the letters in thedistorted picture.
4. Once you have successfully logged in, restart your mail client and tryto access your mail.
So, if you’ve changed your password in gmail, and found that you can no longer log in via your mail applications, give the above a try!