You can't install a backup taken from one version to a core installed with another version.So you need to either upgrade then move, or move and then upgrade.

Or to play it really safe and have the cleanest possible start for the new site: move to a dev or staging site, upgrade, test, cleanup, test again, then move again to the new host.

My personal strategy would be to make a complete clone with backup voodoo, install that clone on my dev system, test it works, make the upgrade on the dev system, test, make a backup, run extreme clean, test, make a backup, copy the upgrade over the existing core, remove the upgrade pointer in config/site, test again, backup, run extreme clean again, test, make a complete clone with voodoo, then upload and install on the new host.

That would give me safety at all stages and the cleanest possible starting point for the new host.