I'm having the same problem with my iPad 2 WiFi, and my wife's "new" iPad (iPad 3) Wifi. The problem will occur when tethering via bluetooth, but not when tethering via WiFi. I prefer to tether via bluetooth because I can start the tethering from the iPad without having to do anything on the iPhone. To start tethering via WiFi you must go into settings and open up Personal Hotspot on the iPhone so you're WiFi access point becomes discoverable.
Here's what I tried:
First I tried resetting only the network settings, that didn't help. Then I tried a full restore, and set up as a new iPad. That also didn't work.
Other observations:
It seems like the problem isn't just limited to iMessage, but Apple and iCloud in general. For instance, after restoring the iPad and setting up as new, I used the iPhone Personal Hotspot (tethering) to connect the iPad so I could enable iMessage (so I could test). First I had to enter my apple ID and password. This part failed, presumably because it couldn't connect to Apple or iCloud at all. I also use iCloud to sync iBooks (bookmarks, notes, last page read, etc), and noticed these weren't syncing either. It seems that most (if not all) iCloud features cease to work when tethering the iPad 2 over bluetooth.
