maknz: Set the APN yourself? You can do that without Jailbreaking.
http://www.iphonewzealand.co.nz/carrier-bundles/xt-carrier-bundle/
From the site:
PLEASE NOTE: Tethering is unavailable on iPhone OS 3.1 and onwards. At this stage there is no workaround for this. If you are currently running OS 3.0.x and require tethering, do not update to a newer firmware as you will lose this function and there is no way to roll back to an earlier version once updated.
I believe that 3.1 is preinstalled these days.