Far too clever for the customers good

Even if your old phone was on 8.3, and the new device is on 9.3, iCloud should be able to restore your data. The problem may be that the new device is on an older version than the old device. This article describes how to fix that:

• In iTunes, or from the Apps & Data screen on your iPhone, tap Set Up as New instead of Restore from Backup. If you already tapped Restore from Backup, tap Back to return to the Set Up screen.
• Follow the remaining steps. For now, you can skip the steps for Apple ID, Touch ID, and passcode.
• Once the set up is complete, update your device to the latest version of iOS.
• Let the update finish, and wait for your device to restart.
• Erase your iOS device: Tap Settings > General > Reset > Erase All Content and Settings. After your device is erased, it restarts and you'll see the Hello screen in the Setup Assistant.

Now you should be able to set up your device again, and select a backup to restore from.

Restoring from an iTunes or iCloud backup when a later version of iOS is required - Apple Support

You can always restore a backup made with an older version of iOS to a device with a newer version of iOS. However, the reverse is never possible. So it does sound like your old device was actually running a newer version of iOS than your new iPhone has on it. All you need do is update that new iphone to the latest iOS release, and then restore your backup to it.