I had exactly this problem; laptop + USB cable + Nokia + Vodafone connected
to the internet whereas same config using an otherwise working bluetooth
configuration did not.

Finally gave up on creating a generic dialup connection and used Vodafone
ConnectMe proprietary software, which worked fine. It's a free download from
online.vodafone.co.uk but I couldn't figure out how to post an exact link to
it on their weird website.