I followed the tutorial detailed here and am now able to use my Palm 755p as a tethered USB modem, connecting to the Internet with an eeePC. My service provider is Alltel, and I paid for the USB modem software (I tried it first - the demo version worked fine too).
The only hiccup I had was also mentioned in the tutorial - I had to force reset the wired connection before connecting with the modem. Otherwise, Ubuntu was holding onto the wired NIC's gateway assignment and trying to use it for the dial-up connection.
FWIW, says I'm getting about 491k download and 79k upload speeds this way.