I have a sprint phone that I connect with bluetooth to my macbook.
Here is what I do to make it work:
1: Set the Personal Web Sharing in the System Preferences->Sharing under Services.
2: Set the Internet tab I clicked on all of the Ports and then hit 'Start'
For some reason I have to disable the firewall, I think that this is just something I've overlooked so I'm still working on that.
Works great, I can VPN into my work via my bluetooth phone and it's usable.
good luck,
bobm