Nope, apparently it's a flaw with Gingerbread update. The only way to make SMS work is either be on WiFi, or if not on WiFi disable 3G by deselecting the "Use packet data" option in the mobile networks part of the settings menu.
This is exactly the sort of reason I wanted an iPhone... everything just works, and I don't have to consider
using this to fix stupid problems with fundamental parts of the OS.