With Windows it is possible for a file stored on the hard drive to prevent the reinstallation or upgrade of Windows, even when using the generic format option on the Windows CD/DVD. Thus, one of the first things I try when I happen upon such a situation is use the free program DBAN to completely wipe the hard drive and start clean. It takes a little time, but it gets the job done where the Microsoft-supplied tools fail. You should then be able to install Vista normally.

Hope this helps,
John