It's a massive bug in Verizon's network that happens to any contacts that are also Facebook contacts (assuming you use the Android Facebook app). Even if you have the number correctly specified in the phone's contacts, the &#$^&! Facebook contact info overrides that.
This guy has a sweet workaround. Basically you go into the Market and install a program called Prefixer by "253 below", and configure outgoing and incoming rules to strip off the +1. Worked fine on both of our Allys.
It figures that the problem traces back to Facebook, but it's a shame Verizon hasn't acknowledged the problem and done something about it in their network. Apparently this isn't a problem for AT&T et al.
