Does iMessage kick in when you're trying to send a regular txt to another iPhone user? This can happen in the case that a test iMessage was successfully sent to then while they were using iOS 5, then they downgraded to iOS 4. In previous iOS 5 betas the app would tell you if the iMessage was not successfully and provide a button to press to send as a regular text message. In iOS 5 GM there is no longer the error displayed, or the button provided.
So what to do? Press and hold on the message text & a pop-up will give you access to the "send as a text message" option.