asterisk users - Jan 2006 - No ringing

We are having problems when people call us the caller hears no rings on the
phone.  We hear the phones ring in the office, but the caller thinks they have
a dead call and just keeps calling back.  It doesn't happen all the time but
is consistent from the same numbers.  If I call from one service provider
(verizon), I hear the ring, but if I call from another (Cingular) it
doesn't.

Any ideas what could be going on?

Thanks