I had the same problem. After a little poking around with network settings I was able to fix it. Here's what I did:
First, I assumed the problem was the bluetooth firmware on the MacBook. I installed a bluetooth firmware update posted from apple yesterday. The problem still existed. I then figured that since it connected momentarily, that the bluetooth connection was good, and that there was a configuration problem somewhere. After a little poking around, I noticed that there was nothing for the bluetooth connection to do, and you cant make an empty bluetooth connection. The problem ended up being that the iPhone's bluetooth connection wasn't assigned to the Bluetooth PAN. In Network Preferences I had to create a new service and attach it to the Bluetooth PAN. I named it "iPhone Internet" for easy reference. After I did that, I went to the Bluetooth icon on the desktop, you know the little one next to the Airport icon at the top next to the time. I chose my iPhone and an option popped up to "connect to network". I did that, and 3 dots showed up in the Bluetooth icon and "internet tethering" showed up on the iPhone. I am sending this post on my tethered bluetooth connection now...

MacBook 2GHz Core2Duo   Mac OS X (10.5.7)