Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
The past few days my imessage has been blue but I was getting the "Not Delivered" on all my messages. Yesterday I signed out of my apple id in message settings, turned off imessage, restarted phone and re-signed back in.

It seemed to do the trick for the rest of the day but this morning imessage went back to being green. Going through the same procedure seemed to fix that too.

At least it is showing some variety in the way that it decides not to work.
Pretty unreliable though. Hello Whatsapp I'm back!
 
Not just iOS

I am having problems with the iMessages app on my iMac running 10.7.4 as well. It seems that it happens whenever I hit the network here at work, because all worked fine at home last night. Started yesterday BEFORE I ran the 10.7.4 update so I know it's not the update that broke it.
 
I'm getting something really weird as well. When my son and I use to send messages (last week) they were both iMessages. He has turn off his iMessages because he has run out of data from his provider, so I get his messages now as texts. But when I reply it sends them as iMessages and of course he doesn't get them. I can turn off iMessage but i'd rather not as it works fine for everone else. Is there anyway of resetting his phone so Apple don't think he's on iMessage? We are both on 5.1.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.