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>
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.