a few simple questions:

Is your phone on vibrate?
I assume since you can pair the headphones that they are turned on right? Is the volume turned up on the headphones?

How did you pair the headphones? as audio or as a car kit?

what about the rocker arm on the side of the Treo, have you tried to turn that up?

when you press internal in SAG (assuming youve turned on your headphones) what does it say as its trying to connect?

simple questions I know but maybe you overlooked one of these things?