I am having the same issue after I called Alltel with a problem over the weekend. They had me wipe my Curve, and download and install the 4.5 code on my device. Ever since then, I have not been able to add a messenger contact - they hang in "pending" state. Weirder part for me is that I get the acceptance note in my mailbox on my laptop, but it never changes from pending on the handheld. I've wiped the device again, removed messenger, resent service books, deleted my information on both my device and the person I am trying to add, and still, no such luck. I too am getting frustrated.