That usually happens when you run out of memory, try deleting old messages, hard resetting phone, and adding a memory card usually fixes it
Posted from my CrackBerry at wapforums.crackberry.com
My memory level is at 16MB way above the 12MB minimum and I also have a 4GB card which I don't think should matter since messages are stored on device memory only. I do battery pulls about once every 2 weeks and I haven't noticed a change. Any other suggestions?