Motorola RAZR V3i / V3t / V3e / V3r

I get the "Messages Full" alert with just a few messages on my phone. It seems to let me accept new messages, but still continues to display the alert and the memory meter shows that it's full. I only have about 20 messages.

Does anyone have any ideas? Has anyone had any experience with this?

This is very frustrating. Thanks!