By default, OS X 10.5.4 lets you set up a mobile phone to act as a Bluetooth modem, but this does not always work. For instance, it doesn't work with a Nokia E61 on the O2 network in the UK.
When you try Connect Bluetooth from the menu bar, you will see Connecting..., immediately followed by Disconnecting ..., and then finally an error saying that it "Could not negotiate a connection with the remote PPP server." This error persists even after taking care to enter the correct username, password, APN, CID, and to change the necessary settings on the phone. Googling on this will also produce a lot advice to install custom modem scripts. This is often misleading, since these scripts were mostly designed to fill gaps in OS X 10.4.*.
In fact, the "connecting/disconnecting" problem is because Leopard, by default, requires a new kind of PPP authorization (MS-CHAP[v2]) which not all carriers support. You can check if this is your problem by checking your console logs, with the Console app, and looking for an error saying "MPPE required, but MS-CHAP[v2] auth not performed."
If this is your problem, the solution is to change this default so Leopard doesn't require it from the Bluetooth PPP connection with your phone. You can't make the change in the GUI. But if you are comfortable changing plist files, the solution is to go to /Library » Preferences » SystemConfiguration » preferences.plist, and change the CCPEnabled property for the Bluetooth-Modem device from 1 to 0. Then reboot, and it should work.
Background: This page has a good summary of the other settings that need to be in place for the Nokia E61 on O2/UK. But it also has pointers to the custom modem scripts which are not necessary and do not address this particular problem on OS X 10.5.4. The essential point about the property change was described in this thread on the macosxhints forums. But a little googling suggests lots of people are having this same problem, but don't realize this fix is relevant to their device.
Mac OS X Hints
http://hints.macworld.com/article.php?story=20080911045249289