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!!
