Ok, I figured this out. There is a 70 message limit on the private message feature, which includes copies of messages that you've sent.
First, go to your "Sent Items" folder, then choose "Show messages from the beginning", you'll see a list of all the messages you've sent in the past. Delete some of those to free up space in your box.
If you want to avoid this happening in the future, then make sure you uncheck the box labeled "Save a copy" when you are composing new messages.