I've been USB tethering with my Nexus S for over a year with no problems. Went on vacation last week, came back, and discovered tethering no longer works.
The phone actually thinks its tethered just fine and shows the tethering icon in the top menu bar as normal. But Ubuntu's connection icon in the top right sys tray just sits there spinning, unable to complete the connection.
I also tried Wireless Hotspot and Bluetooth, but neither seems to work either (Hotspot has always worked in the past, never tried Bluetooth tethering till today). Normal wireless routers (home, library, starbucks, etc.) still work fine, it's just connecting to my phone that appears broken.
No idea what's the problem, a recent update maybe?