Upgrade from iPhone 3G 4.2.1 to iPhone 5S 7.0.4
I just upgraded from 3G to 5S and at first had the same problem. What I learned in another chat was that prior to restore I had to update to IOS 6.1... Once the OS was updated, I backed up the 3G and did a restore to the 5S from the latest 3G backup. It took a long time, but was well worth it.