I figured out whats wrong. I'll post for the benefit of other Treo newbies who are still getting the hang of the technical "delicacies" of the Treo.
I accidentally set the keyboard into discoverable mode AFTER clicking connect on the Treo. You have to make sure the KB is in mode before clicking connect on the Treo. If you don't, you get the "connection failed!" error and the only way to fix it is to soft reset. FYI, if you realize you've hit connect and the KB is not yet in mode, you can simply quit the keyboard app., restart it and follow the protocol without any problems. You just have to quit before the error comes up. Also, thanks to those who provided info on soft resetting.
