Hi John, since you have a backup you likely had an iPhone before. Did you trade it or sell it and if so did you erase it (and thus remove it) from the list of devices under your Apple ID? I suspect that it is still showing under your Apple ID devices.
Don't know if this will work but may be worth a try. Initially set up your new iPhone as New without the backup but using your Apple ID. Then go to Settings / Apple ID and see if your old phone shows up there. If it does, select it and remove it. Then erase your new phone and try to set it up with the backup. This is a pain, I know, but it is the only option that comes to mind. Hope it helps. If not others may have better ideas.