You're with Windows? did you clean out your registry? This is risky, but I would do this;
Uninstall Perl, then go look for where Perl was installed and delete what's left.
Run REGEDIT and delete every reference to Perl and the mentioned dlls in this thread.
I guess you already know that fooling with REGEDIT can cause you to loose/damage your Windows, good to back it up before you start.
After you're done, reboot first, then re-install
Probably, since you downgraded instead of upgrade, it wasn't expected and things from the upgrade might have gotten hung up in places like the registry.
Here's the Perl I use and works It's dated 2006 , probably same as what you got.