This has happened to me alot in the last week. But only with two specific contacts. I dont have a huge contact list, but after clearing out all messages, it seems to work fine for awhile.