Make sure you are running the latest versions of firmware for the Treo 650. I happen to have an unlocked edition so this is very easy to fix from PalmOne.
I recommend going with the latest but this isnt a deal breaker. I am going to assume this from a total newbie position as yes, you can use pppd or wvdial from CLI. For our test we will be using Ubuntu 6.06 and Gnome-ppp. To enable “tethered” mode on the Treo you maybe lucky and dial #*83843733. I was unable with GSM and Cingular and instead used this software which works wonderfully. If anything they also officially support Linux.