Many seem to have problems getting to share their 3G internet connection over bluetooth between their iPhone and their Mac. It’s called Tethering. And if you look up this issue, many posts will just tell you to forget it because your carrier probably doesn’t allow it.

Persistence brought me to a solution. Macbook was telling me the pairing was successful. iPhone was telling me Tethering was ON, but that my Macbook had been discovered and “Not Connected”. The solution lies with fixing the Bluetooth PAN settings on the Macbook. But first remove all links that the iPhone and Macbook created between them during previous pairing attempts.

Here’s the blog post from @Peaz2.0 that tells you how to reconfigure Bluetooth PAN. When you’ve done it you can tether your iPhone 4’s internet connection with your Macbook. You will know that it’s working because a blue bar will appear on your iPhone just like the one below.