I know this message comes up from time to time. For me, this time, it happens when trying to delete old messages from the UCP.
In the "message list", check the box to the right of a message, then at the bottom of the page selecting 'Delete marked' from the drop down, and press Go... I get "The submitted form was invalid. Try submitting again."
If on the other hand, I view a "message" and click the 'x' at the top-right of the message, I'm prompted 'Are you sure you want to delete this message?'. If I answer Yes, the message is gone.
As suggested in related topics, from the ACP I used the "Purge the cache" feature but the error message continues.