I had this problem some time ago. I don't remember the amount but I had to remove a lot of messages before being able to send again.

@Paul, Tick the selectbox behind a message and then select the 'selected messages' button and then select delete, to remove specific messages.