So, to ease the pain, heres a how to use your Nokia to connect to the Internet in Ubuntu. Im using Ubuntu Gutsy Beta 4 and a Nokia N82. Everything should be pretty much the same for older Ubuntu versions and other Nokias.
Read it in this blog
OS X is without a doubt the easiest OS for configuring Bluetooth devices. Adding phones, keyboards and headsets is (more or less) as easy as it could be. Windows is way behind. You can add your phone, but where OS X automatically sets up the phone as a modem connection, you will have to download some PC Suite crap or hack your way onto the phone. Ubuntu is somewhere between Windows and OS X, but (sad to say) closer to Windows.