SUCCESS!

The Bluetooth method described above is far and away the easiest way to get tethering working in Linux.

I'm running Ubuntu 8.04 and after about a month of trying, I was about to give up and go back to dual-booting Windows..

All I had to do was edit the config files as outlined above for my Pearl's MAC address and my phone number (of course). I had to install/compile absolutely NOTHING!!

A big THANK YOU to SDNick484!!