I can confirm this works! Speed was 300/275 via BT PAN, then I plugged the USB cable in and got speeds of 905/318 (Speakeasy speed test). I'm in Sacramento (HSDPA) via the MediaNet wap.cingular APN. Looks like the BT 2.0 craps out at 300kbps.
My steps (I had a few extra to add to yours)
-I unpaired the devices on both the phone AND the MacBook
-Paired the devices FROM THE MACBOOK (Laptop sees that PAN is available)
-Unpaired the laptop ON THE PHONE side
-Paired the devices FROM THE PHONE (Connect via Bluetooth in the ActiveSync program)
I had to do the last two steps because when I paired from the laptop, the phone did not pick up the ActiveSync service, and so Missing Sync wouldn't sync via BT. Pairing from the phone side through the ActiveSync program fixed that up, and the laptop didn't need to make any changes so the PAN was still there.
Maybe if you pair from the phone first, you can avoid the last two steps? I'm not going to risk breaking my working setup to test it though. ;)
Syncs via BT, and does PAN via BT now! Good thing you had to re-pair the devices =)