There are some instructions here at Re: HELP! Premiere Elements 9 MSXML Error?? but Solution 2 does requiresa certain amount of expertise.
[EDIT] - ha! I see Bill has beaten me to the 'Post Message' button
Insanity is hereditary, you get it from your children
Sometimes it pays to be on -8 GMT...
The suggestions found by a previous post did not work for me -- but please don't let me discourage you from trying them. The only way I could get this to work was to remove the msxml installation from the image and replace it with something else which would install (see http://forums.adobe.com/message/3229454#3229454).
From what I can tell, the OS is preventing any updates to an existing MSXML library installation. My system already had MSXML 6.0 SP2 installed. PrE is attempting to downgrade this to 6.0. The OS doesn't like it because of some security issues (see http://support.microsoft.com/?kbid=968749).
I'm curious to know if you have SQL server or Visual Studio installed on your system. This is where the MXSML 6.0 SP2 patch was installed for me.
It would be great if you can give us following log files in order to debug this issue.
Location: - Go to Start Menu -> Run-> %temp%
Also, please let us know if any other version of MSXML is installed on your system before installing Premiere Elements.