Non-root tethering app with Ubuntu client for Moto Droid on Verizon
Try AziLink (http://code.google.com/p/azilink/).  You will need to do a little setup on your Ubuntu machine in addition to loading the app on your DROID, but it will work without requiring you to root your DROID.  This is a USB tethering solution that I have used in the past with my Ubuntu netbook to great success.