Because AT&T uses different LTE bands than Verizon. AT&T is in the lower bands and Verizon starts at 747 MHz. It's a physical thing.
And unfortunately, Europe is using 3 completely different bands (though their rollouts are much further behind Verizon and AT&T). Verizon also has some AWS space it could use later, and AT&T may eventually decide to use some 1900MHz space it frees up from 2G for LTE. All this means is that we may need "octaband" LTE phones if we want "world phones" in the 4G era. Every generation keeps getting worse (3-4 bands were enough for 2G, 4-5 bands for 3G).