A few people aren't aware that we can only have 22 PM's saved at any given time, including your sent.
To save ones you want to keep, download as a text file or .csv..you will see at the bottom of your PM listing a button that says Selected Messages. Click on it and you will get options to delete, save, etc...:)
http://i30.photobucket.com/albums/c3.../DYsavepms.png
Once downloaded, go back and delete those and then you will have room in your PM's.