Codeman,

Carriers are really getting away from allowing phones from other carriers on their systems because of #1: money - new phones have links to online services like "Get It Now" & "Axcess Apps." Sprint calls these BREW & Java applications "Vending machines" inside the phones because when you get to using them they bring in big bucks to the carrier. Anyway, they really are not reprogrammable between carriers, but the 7135 doesn't have BREW so that doesn't matter in this case. There are other software issues, too, though, like Mobile Web IP addresses & differences in operating software - an example is Verizon's Motorola T720 was an unstable POS that froze constantly, causing them to replace it with the T722. Alltel's had poor reception, but was stable.
The biggest issue is the PRL - prefered roaming list - telling the phone what network to use in every square mile of N. America. Every carrier's is different. If your phone's previous owner had Verizon's PRL overwritten, no prob, just call over the phone (800-alltel-1) & tell them you have another phone you would like to use and mention NOTHING of Verizon.
But before you can get this done, make sure the phone is capable of locking onto Alltel's service or else it will have to be flashed at a store, which you already have seen won't get done. Just turn on the phone side, and when it comes up with a steady signal, dial some non-real number like *48 or something and press send. If the message stating you cannot complete the call is from Alltel, then call them up & give them the esn. if you get someone else, like Verizon, US Cellular, etc, then your PRL is not set to Alltel and you cannot update the PRL without visiting a store.

Hope it helps