I have this same problem on stock VZ 6.5 ROM. The solution is to deleted messages.
Sucks, because one of the things I liked about Windows Mobile Smartphones is the ability to store a lot of stuff. What's funny is on my old Cingular 3125, I had thousands of messages and that didnt phase that little phone.
Now this "powerful" Touch Pro 2 cant handle a few hundred
