This is easy, just boot to your unfortunate version of 8.1, and go to your Desktop. Stick your disk in the drive.
Then browse to 'Setup.Exe" in the installer media, and run it. It has to be run from within Windows or it will not work. When the setup screen brings you to the choice of "Upgrade" or "Custom Install" choose "Upgrade" and then reinstall it. Use your new key to activate, and call the 1-800 number if problems.
Be warned, some Windows 8/8.1 installers do not have the Upgrade as part of the installer, if it will nto allow you to upgrade, you have to get a different disk. So when downloading or buying a new version, make sure it is a disk that allows upgrading. Usually, if it is the exact same version you had, it will upgrade, this is called an In-Place Install.
These OSes use a KMS activator, when you re-install, the activator will be deleted. Usually, it also exists as a program from within Program Files, this has to be uninstalled as well. Just look for anything that says "KMS"
I've probably said too much, but you need to know what to delete.
The other option you have, is going to the Activation window and hit "Activate with a new Key"
If your unfortunate copy of 8.1 says "Permanently activated" that button wiull nto be there, and you'll have to use the SLMGR.VBS command to enter a new key. Just type SMLGR.vbs /? and it will show you the command for entering the key manually.
I would probably do this first- And if it fails, you should call MS, explain your problem, give them your new key, and they'll give you one that works with the OS that was installed.