I was able to resolve the problem using the method "NOT PREFERRED".

My OS is Windows XP Build 2600 SP2. My Visio version is Professional 2003 SP1.

I am certain that the scenario you describe around the Preview install and un-install is waht happened in my case. I looked for and could not find the install package for the version of Preview I had installed. I recall that the version I had installed was not the last Preview release.