I was unable to use dial-up over my T-mobile phone until I disabled IPV6 in Leopard. The command to do that is:

sudo networksetup -setv6off <interface>

For me, interface was Bluetooth for the Bluetooth connection and the name of my phone for the USB connection. This will depend on whatever your phone calls itself over USB.