Alright everyone. After almost 10 hours of phone time with 8 different departments within both AT&T and Apple I have a fix. My phone works and I believe if you do this same thing you can get yours to work as well. I have my original account, and my original phone number, with no new charges incurred.
Remember, YMMV. This worked for me, and if you have the same problem as me this should work for you too, but no guarantees.
Prerequisite : If you haven't already, restore your phone to factory defaults. I forget exactly how I did this, it involved holding the home button for 30 seconds or something, I'm sure you can google it.
First, connect to iTunes and try to activate your phone as a new customer. You'll end up with a message that says that your activation will require additional time. After 5 or 10 minutes you'll get an email for the iTunes activation system with an order number. That order number is the key.
Now call this number : 877 800 3701
I'm not sure what this department of AT&T is but this worked so roll with it. Select option 3 from the menu and enter that order number you got in your email. Explain the problem to the tech. He or she should ask for the IMEI, CCID, AT&T Pin number, and SIM ID number.
The tech was able to fix it but it took a really long time. I was on the phone with him not saying a word for about an hour and 15 minutes. The tech said to wait 15 minutes and try and activate, but it still didn't work. Do this before bed and then sleep on it. It took over night for whatever they did to work. When I woke up my phone worked with my original account and my original phone number!
Edit for clarification : Make sure you tell them that you don't want a new account, that you want the phone to work with a preexisting account. Tell them that you want the SIM and the iPhone that you have in your possession to work with your current mobile number and that you only tried to go through iTunes to get your phone connected back to your original number. They can do it, but no one at AT&T except this department seems to know how to do. It's a long process so they might try to get out of it, tell them you want it fixed, and you don't want to talk to anyone else.
Good luck all. If your in the same boat as me (replacement phone not working with preexisting account) this should do it.
Message was edited by: Adam Drew2