Tethering Problems Between MBP and iPhone 4 Resolved
After some tinkering the PAN finally works. Edge case bug, me thinks.
This morning while attempting to tether my brand new iPhone 4 32GB to the almost new 2010 Unibody MacBook Pro, I ran into a series of problems. (Why do this? Because I want to create a PAN, or a Personal Area Network. This will allow me to use my iPhone 4 for wireless Internet access while out and about.) After four attempts at pairing the two in an effort to enable tethering, I had to hit the intertubes to find a fix. Unfortunately, others had similar problems.
So, Navigating to Settings >> General >> Network >> Internet Tethering and flipped the switch to 'on'.

Then it was time to initiate the pairing from the MacBook Pro. Now to start the pairing on the iPhone. Navigate to Settings >> General >> Bluetooth and the phone automagically starts searching for the MBP. Poof! Once the Mac sees the iPhone it gives you a security number to ensure it is syncing to the same devices, like here:

You see the same security number on the iPhone, and hit the Pair button.

Much to my chagrine, the below "Pairing Unsuccessful" message showed up each time I tried to pair the devices.

After the fourth attempt, I checked Console to see if there were any interesting messages.
Bluetooth Setup Assistant[425] starting pairing
Bluetooth Setup Assistant[425] Pairing failed with 'Stu Thompson’s iPhone': error 0x10
Yup, that's interesting. Out in the Googleverse there are plenty of folks having all sorts of problems pairing their iPhones and MacBook Pros, in an attempt to tether or otherwise. There is information about updating the Bluetooth firmware, but that was not relevant to my brand-spanking-new MBP. So, after some peeking and poking, I decided to delete the existing Bluetool PAN on the MBP.
And that worked! (To delete the old PAN, just select "Bluetooth PAN" in the Network Preferences and then click the little - button at the bottom left.)

What I had failed to take into account was that there was a previous tethering relationship configuration in the original Bluetooth PAN. Several weeks ago my buddy Lincoln and I had paired my MBP to his iPhone so that we could get on the net while discussing some technology mumbo jumbo at Imagine.
A little bit frustrating. Although this is an edge case situation, Apple could and should make the tethering process more robust. Responsible Stu thinks he should file a report with Apple. Pessimistic Stu thinks communicating with Apple is too opaque and unrewarding. Stu's wife thinks he should stop geeking this Sunday morning and pay more attention to her. Two against three: no bug report.