It turned out to be extremely easy to use the BlackBerry Curve's tethered modem support from Ubuntu. This allows the device's dial-up networking capabilities to be used to access the internet. This will work with either a Bluetooth or USB connection. The instruction for using Bluetooth can be found here. Unfortunately my BlackBerry is a corporate phone and using the tethered modem costs an extra $15 per month. So I'm out of luck at least for now.