After upgrade to iOS 6.0 I noticed that my iPhone sending SMS messages ok but not iMessages and this may have been on happening even before the upgrade. A quick search revealed a simple, yet somewhat embarrassing, solution - make sure, the feature is turn on. Note that iMessage has to be on for iMessage to work. To turn on iMessage go to: settings --> messages--> and make sure iMessage is on. It worked for me!