AFAIK the iPhone does not support a number of somewhat important protocols in the bluetooth stack.

DUN/SPP is among them [Dial Up Networking] which is, generally, the most used network protocol. I gather this is what you are attempting to do with bluetooth via the iPhone, no? This is likely the trouble you are encountering.

Alas, the iPhone also doesn't support A2DP and OBEX which I suspect is likely a bit of a disappointment for some users as well.