The good news with Fedora 12 is an extremely easy dial-up-networking connection with bluetooth devices. The sad thing is, Nokia E55 doesn’t have PAN type connection via bluetooth. The good thing is, DUN type connection is almost that easy.
Create connection to your mobile through System > Preferences > Bluetooth > Set up a new device wizard. Also create connection using NetworkManagers Edit connections > Mobile Broadband > Add wizard. This should be enough for PAN, but not for DUN connection used in Nokia devices.
For dial-up-networking, you need to install Blueman application, for example by using terminal.
sudo yum install blueman
Then open System > Preferences > Bluetooth Manager, select your phone and choose Device > Serial ports > Dialup service. Now Blueman tells, there’s a connection available on NetworkManager. It’s as easy as that.