I'm misremembering - it was FaceTime, not iMessage. Whoops.
Unless I'm continuing to misremember, there was some patent issue that blocked FaceTime from working over cellular on the first version, but it was cleared up when AT&T finally accepted that they were the only carrier not supporting it.