(1) AT&T paid for limited exclusivity
(2) AT&T is using HSPA+, which is part of the same modem. Verizon is using LTE, which is a whole different setup and requires more circuitry (SIM and, I think, a separate chip).
Because of (2), expect most Verizon "4G" phones to be bigger and later than their AT&T counterparts for a while. (Bionic v. Atrix, Stealth v. Infuse, etc.)