Let's ensure your messaging app is running in top form. Have you been able to head into, Settings > Applications > Manage Applications > All > VZ messages, and clear data and cache within the app? You may need to force stop the application first. If this does not work, please remove the application and re-add.
Follow us on Twitter @VZWSupport