No not a fresh install, but a repair install. Keeps all your programs and such and saves you a lot of head ache
Do NOT use the recovery cds.
Need to get your hands on a Vista SP2 disk and do a repair install with it. Might have to get it off the net (A non hack version, just a straight copy of the disk) And I only recommend this because you already own it, you just need an updated setup cd.
Something is wrong with your registry from what I can tell. You should not be having this trouble.
Also just to make sure I cover all bases, you are using an account with full access correct, an admin user account? (I am sure you are just want to be sure)
Shane