I just did a fresh Ubuntu Karmic reinstall after an ill-conceived upgrade to a Lucid Alpha, so I had to try and retrace my fairly muddled steps in configuring iPhone tethering.
Because I had a fair idea what I was doing this time it was pretty easy, so I figured I'd best document the steps for the next unfortunate soul trying to do the same. I'd also be interested to hear if the same steps apply to Lucid once it's out of Beta.
The first thing to do is get tethering enabled by your operator. For some reason O2 can only enable it overnight so make sure you get it well before you'll need it. Once it's enabled, you'll find your phone has a new option under Settings->General->Network->Internet Tethering. Make sure you turn it on in here and then forget about it - it's only enabled for devices that are paired over Bluetooth or USB so there's not much of a security worry.
The next step is to get the Ubuntu side sorted. The best bet is to install the Bluetooth Manager widget Blueman, which will replace your existing Bluetooth widget. Blueman is much better than the default simple widget, but unfortunately either the way the iPhone exposes its network access point is non-standard or it's a bit advanced because the older version of Blueman in the Ubuntu Karmic sources is not capable of connecting - you'll need to install a newer version from Blueman directly.
The best way of doing this is to add the Blueman PPA and install it from them via apt:
$ sudo add-apt-repository ppa:blueman/ppa
$ sudo apt-get upgrade
$ sudo apt-get install blueman
I found after doing this the old bluetooth widget was hanging around, but restarting X fixed that.