Yeah, we had the same problem, and there's an easy fix.
Here's the problem:
You don't have the most recent version of the iOS on your phone. You, like me, probably got the phone from a carrier (like Verizon) rather than the Apple Store. At the Apple Store, when they open a new phone, they probably update it to the most recent iOS, with the updates since the phone was shipped. At Verizon, and the other carriers, they don't. So you have an older iOS on the phone. And that iOS apparently has a bug that doesn't allow it to do backups from older iOS versions, like the one that you were using on your older iPhone.
That's my guess, anyway, based on how I fixed mine, and the fact that there haven't been a lot of people with this problem posting online about it. So it only happens to some people who (1) get their phones from carriers, and (2) don't have the most recent iOS on their old phone (i.e., they didn't do an update).
Here's how to fix it:
1. Go into Settings --> General --> Software Update. You'll probably find that there's a software update available for your new phone. Install that update. That will take a few minutes.
2. Now that your phone is updated, you need to re-install the phone: Settings --> General --> Reset (scroll to bottom) --> Erase all content and settings. Sounds scary, but right now you don't have anything on your phone anyway. Seems stupid to have to do this, since you just did it, but you need to do it again because Apple doesn't (for some reason) allow you to do an install from an iCloud backup except as part of the new installation. That will also take a while.
3. When the phone reboots, it will be like a new phone. Just answer the questions as you normally would if you were getting a new phone. It will automatically pick up your wireless account, so don't worry about that (or at least it should). When you get to the account question, put in your account. When you get the choice for how to install, choose your iCloud backup. That should work.
Good luck!