Epi, I bet you're getting that message about your mailbox being full because you have built up too many sent items. In the upper right hand corner of the PM message box there is a drop down that'll let you choose from INBOX/SENT ITEMS/SAVED MESSAGES/ETC. I believe you are only allowed a certain number of each type and if any one of those items reaches it's limit then your mailbox acts like it's full. So just go and delete all your sent items.
If the sent items section isn't full...then, nevermind.