Isn't tethering done with Bluetooth?
I've seen a video telling how to tether with another (Xfce-based) GNU/Linux system before; on there, you enable bluetooth, pair with the phone that has tethering enabled, and then choose the bluetooth thing from the wireless connections list. I don't know if GNOME is different.
