I finally took the time to figure out how to tether my laptop to my phone. Yeah - I know, lots of people have done this but I couldn't find a straight forward walk through for my scenario.
You can find the walk-through here: BlueTooth tethering Ubuntu 9.04 to a Rogers N95