What do you mean your iPhone overheated? You need to give details and expand on your issue, otherwise no one will be much of help, just like the ATT guys, they'll refer you to Apple. If you used it in hot weather or warm conditions, it will most likely heat up (which is normal). Get a replacement now, if you are under warranty they will repair/replace your iPhone with the SAME model only free of charge. If you are too far from an Apple shop, you can request an online service, where they ship an empty box to put your iPhone in and send it back to their repair warehouse where they can look into the issue.
Never expect that you can get an iPhone 4/5 replacement since they won't replace it, unless all the Apple stores in the country have run out of your iPhone model (which is a rare exception).