I have a 4s (CDMA) running on 5.0.1 firmware. I just tested iMessage on 3g and it seems to be working fine for me.
Here is a little something I came up with in a quick Google Search. -->
"Enorym writes...
don't worry.. I just found out you can only use iMessage over WiFi.. which I think is total BS..
Not true at all i have been using imessage since ios 5 beta 1 and it works over 3G
It would only work over wifi on the ipod touch and non 3g ipads as thats the only source for data..
Also if there is no data connection it will default to sending an sms"
The site that came from can be found...
HERE!
EDIT-- Also, it may not be your phone that isn't working with iMessage. The recipient on the other end of the text may not have their iMessage on. I've had that issue with iMessage texting (well iMessaging >.<) my girlfriend. She never has her's turned on so all my messages are sent as texts.