My wife and I both get this issue fairly frequently. We send a message (from our iPhones or iPad) and then it'll be 'Delivered', 'Read', and then the red text 'Not Delivered' appears even though it was definitely delivered. Both iPhone 4, iOS 5 not beta. MBA and MBP running OS X 10.8 using the messages app. It's really irritating, we have no idea if things are going through or not, just really terrible. Everything is fully in sync, but we get these messages. I think it has something to do with our Messages app running on OS X because we never used to get this behavior.