It shouldn't be locked in the first place. All phones purchased through AUP are supposed to come unlocked. I would suspect your phones are unlocked and Verizon is just pulling their typical crap about not activating phones not on their "white list". That was supposed to be a thing of the past, but others have reported still having trouble getting Verizon to activate non-Verizon phones.
But the thing is that at&t confirmed that the phone is locked. I'm really confused. I'm wondering if the Apple Store sold me a locked at&t version instead of an unlocked at&t version as they should have through the upgrade program.