There are a few things that could prevent this:
Your recipient needs to have iOS 5 and iMessage enabled as well
Not enough data to send iMessage SMS (low coverage area, perhaps?)
Use an Apple ID to send iMessages rather than your phone number. It should work under your # but sometimes it won't. A good way to check for this and my first idea is to have your contact # listed under iPhone and not Mobile.
Can you try this:
Open the Messaging App, tap the write new message, then tap the icon, select the name of your contact, then select the email address associated with iMessage. If this doesn't show "New iMessage" then there might be something wrong with your connection to the server. Either an Internet connection problem as mentioned above, or most likely a login problem.
I had this problem before in Settings > Messages > iMessage is ON but it shows waiting for activation. What I did was I changed MMS setting from ON to OFF, disconnected from the network, then turned it back ON. It then asked me to login again with my iMessage userID and password.
Mine didn't work for 2 months and this fixed it, so I posted it in another discussion and have been getting "thank you" replies nearly daily:
Just update your date/time settings:
>> Date & Time
>>> Set Automatically: Slide "ON"...If it's already on, then slide it off, chill for a bit (maybe restart it), then slide it back on.
I am using an iPhone 4 with iOS 5.1, but other users with 3GS, 4S, and even iTouch devices replied that it worked.