I took out the AT&T sim card first! Then you can plug it in iTunes and run through the setup and you'll get the message.
I called T-mobile to switch from my regular sim card to the micro, while inserting it in the iPhone and setting it up at the same time.
Just as long as the AT&T sim card isn't in there, you're good.
AT&T sim or not, it doesn't matter. I used AT&T sim to both activated and unlocked through itune. Phone is working good with Tmobile right now.