I just got off the phone with RIM last week because of BB Messenger probs..after about 1-2 hours of trouble shooting they had to walk me though a complete format of the phone then re-install everything. That might be what you might have to do also...their phone # is 1-877-255-2377. Be warned it took about 2 hours of being on hold before I got someone to talk 2, so call when you can relax and watch something on the idiot-box while they sit on speakerphone
Good luck...Feel free to add me to your list if you want someone else to test it with...I know how essential it is to have someone to test things out with as I was in your shoes only last week.
btw - do u use Cingular by chance? BB Messenger does not work with them