Not only that, but the AT&T iPhone was connecting to the same network prior to the update that it was after the update.
LITERALLY the only difference between 5.0 and 5.1, regarding the network, is whether they call it "3g" or "4g". It's the same speeds. Apple could lie to you and put a 4g icon on your VzW iPhone too, but it wouldn't make it any faster than it already is. Same as the AT&T change. Pure marketing, nothing more.