Given that you're simply wanting to deactivate the installation, rather than fight with the old system perhaps you should call Adobe Customer Support, describe what you want to them, and ask them to deactivate your old activation directly.
They're usually pretty good about helping with activation issues - though we've heard a very few complaints here on the forum that telephone support sometimes tries to put off helping folks with older versions. I suggest being polite and patient and just describing what it is you're wanting to do without naming the version at first. Have your Adobe ID handy, and your serial number. There's certainly nothing wrong with wanting to activate an older version on a different computer.
For those of you having the same issue, I found that insufficient disk pace can be a cause for the deactivation for fail too.