Thanks for the explanation.
This thread is also discussing the same issue: https://forums.macrumors.com/threads/1251571/
It seems that phones ordered from the Apple store are locked to the number they were ordered on, no matter if AT&T switches the SIM/IMEI to a different line in their system before activating.
A couple people in the other thread have had success activating the 4S with a SIM from the line it was ordered on and then switching back to the line they want to use it on.
So what to do if I already had AT&T switch the SIM/IMEI before trying to activate the new phone? I can't activate the new phone because the SIM doesn't match the number on record. I can't use the old phone because AT&T has switched the SIM/IMEI. They say the can't switch it back because the old SIM is no longer usable.