This sounds about right. I had a feeling the phone wasn't the problem in and of itself but AT&T's recognition of the equipment. In regards to changing my account's IMEI... Do you think, say, using a Lumia 520's IMEI (I just ordered one and a nano SIM converter) then switching back might possibly resolve this? That is to say I wouldn't tell them about switching back to the unlocked RM-985 Lumia 830. (;
Yep.
The imei from your 520 won't work because it is not LTE capable. It needs to be a imei from an AT&T branded and LTE capable phone.