Aaron Gerber,
Actually still easily done, but you will need to know the ESU authorization codes for the core Desktop product and each of the extensions. All of them will often be found in an "authorization" file that should have an extension of *.prvc in email or on the local system.
The process is to run ArcGIS Administrator --> Support Operations --> and Deauthorize... it should return the fulfillments for the core ArcGIS for Desktop and any extensions, back to the FlexNet Publisher services at Esri Redlands.
Then, with the license "fulfillments" returned to Esri and available for reuse, you can use the same Authorization file and run the ArcGIS Administrator --> Desktop --> Authorize now... wizard. You can manually edit the existing authorization file to remove extensions no longer needed, and could also just enter all the details by hand into the Wizard.
Proceed through and do the 'authorize now via the internet' for the simplest completion.
Post back if still stuck.
Stuart