The phone is fine using WAP and also GPRS from the desktop, but now gives an error "subscribe to GPRS first" when attempting a connection from the iPAQ. I have seen a number of other people reporting this behaviour.
To cut a long story short, here is the solution:
The 4150 (and probably all WM2003 PPCs) uses an init string of ATE0V1&C1&D2
The laptop BT modem driver (IVT BlueSoleil) uses a slightly different string: AT&FE0V1&D2S0=0S7=10 which clearly works on my laptop.
On the PDA, this is located in the registry at HKLM\Drivers\Unimodem\Init\2 and can easily be changed by a registry editor. After this change, GPRS is working flawlessly!
Now if only someone had a proper VPN client...
Enjoy.