Two most likely problems are (a) something's wrong with Windows Script and (b) the Active-X control used by the TD to display file dialogs, etc, is not installed or working properly or is blocked.
*Technically*, your security settings should not matter one bit. Although the TD runs inside of IE, it runs in a special mode where security settings should not affect it. Whether or not that's the actual case with all versions of Windows multiplied by all versions of IE, I don't know, and I frankly doubt. So you may fiddle with IE's security settings, but I don't know what good, if any, it will do.
My first suggestion would be to re-install Windows Script. This is a really solid fix-all for TD problems. Unfortunately, as far as I know, Microsoft has not yet released an independent version of Windows Script for Vista. So, you've got it installed, but you can't go and simply re-install it by downloading it, not with Vista. And this is unfortunate, because Windows Script is frequently corrupted.
Since you're on Vista, my next suggestion would be to re-install IE. I'm not certain, but I think this would re-install (or at least update) Windows Script as well. But since you've just "rebuilt" your Vista installation, I don't see this as being helpful.
So, the only thing I have left is to see if you can get the Active-X control re-installed. Here are some instructions for trying this:
First, close all instances of Internet Explorer you may have open.
Next, open Windows Explorer, and navigate to "C:\Windows\Downloaded Program Files". You should see an entry named "Microsoft Common Dialog Control", or something very similar. Select this entry and delete it. It is also possible you won't see the control listed here, that's OK.
Next, navigate to "C:\WINDOWS\system32". Delete the file "comdlg32.OCX". You may not find it here, but you should. If it is not present, it is possible that another program on your PC installed the same control, and installed it to some location other than "C:\WINDOWS\system32". In that case, you may need to use Windows Explorer to search your C: drive for the file. If you find it elsewhere, you may want to rename the file instead of deleting it. That way, just in case something does go wrong with another program installed on your PC, you can rename it back to fix the issue.
You shouldn't need to restart your PC at this point, but it wouldn't hurt. I'll leave that up to you.
Finally, re-run the TD and see what happens.