Originally Posted by BBAdmin
This is a service book issues. Delete the Service Books on your problematic devices and then re-send them from the BES server.
That didn't exactly help. I deleted all the service books except provisioning (you can't delete that) and then resent service books from my BES, and I still had the same problem.
I backed up my device, then I used app loader to wipe and reinstall the OS and 3rd party apps, did a sync, restored just the messages from the backup since everything else came via sync, and now everything seems to be fine and I can reply to messages.