I had a similar problem when testing the forum moderation functionality. What I found was that when you delete a moderated posting it seems to decrement a count in the database. This number can actually go negative while testing when you have posts in the forum before you change it to Moderated (and delete some of them). When you post a new message it increments the value correctly but it still might not become a positive count.

The table is forum_forums and the column is PostsToModerate. I wrote a small fix script to use while I was testing (I think this is only a problem because I was deleting messages while testing).

SQL:  Update forum_forums set PostsToModerate = 0 where PostsToModerate < 0

After you do that cleanup, create another moderated post to test. If you are already live with moderated posts in the queue this may not work. You would have to figure out how many posts are in the moderation queue and update the PostsToModerate to that count.