Aha! Looks like in phpBB version 3 and up, private messages remain in the outbox until the person you're PMing reads them. I wasn't aware of this upgrade but it seems pretty useful. It allows you to edit the message before they see it if necessary. Has the person you're trying to PM been on recently?
If that's not the case, try checking to see if your sentbox is full. Deleting old messages allows the new ones to send. Let me know if you find that either is not the case! I'll be doing a quick test of my own to make sure the problem is just the former, but other than that I hope that answers your question.
