What are you , using BES or Webclient.
If webclient ,is it 1.8 or 2.0
If 1.8 , do you have auto aging setup
__________If above does not apply
Go under Options and Status : Check the Free Memory space
___________If does not apply
If you are using BES are you manually Filing messages to a different folder manually?
________ If not
Call your Carrier Support for Blackberry,ask them to walk you running Application Loader to re-install the Handheld software on the unit.Try not doing a backup restore during the upgrade process.