MacBook + iPhone 3GS + Mac OS X 10.6 (Snow Leopard) + Bluetooth + Tethering = Issues? Solved!

So for the longest time my iPhone and MacBook have not played very well when I need to do Bluetooth Tethering.

Long story short, the resolution is to go to System Preferences > Network > delete Bluetooth PAN and create a new Bluetooth PAN.

Don't bother with pairing and unpairing - it's nothing to do with that.