Your phone should not have any idea if the call is coming from Verizon or
Sprint versus T-mobile, Cingular or a fixed line. I cannot see why the
problem could be on the phone. Anyway, have you tried your SIM-card on
another phone? Perhaps the caller number from Verizon/Sprint is not provided
in a compatible format and makes the phone reject (still shouldn't happen as
far as I can see).

I think the small icon you see when somebody from Verizon/Sprint calls you
is actually a "padlock", indicating if ciphering is on or off (padlock
closed or open). This again indicates that the phone is answering to the
page from the network, then starts signalling on an SDCCH but for some
reason the phone or the network quit.

Something like this could happen if the network only checked IMEI at this
phase and the phone was black listed but it can't be because you can place
calls and receive from T-mobile etc.

Also if you had some incoming call barring activated, the network should not
page the phone, and I cannot see barring for Verizon but not for Cingular
(like all incoming barred, incoming when roaming etc.).

Hope you get the problem solved anyway (you could ask the persons calling
you to change to T-mobile/Cingular ;-)