I was having the same problem a couple of weeks ago and tried all the suggestions I could find to no avail. After a couple of days of frustration I made an appointment at my local Apple Store and was in and of the store in less than 10 minutes with a new iPhone at no charge.
Tried reset to no avail. Have not tried restore yet. No apple store within 2 hours of here. Think best buy can help? AT&T was no help. Spent an hour at a kiosk already today. Thanks for helping everyone.