I am currenty struggling with this problem myself. I'm glad to hear that some of you have been able to get it to work. I had pretty much given up on it and was just about to gripe about it here on this forum when I noticed this thread.
Install, remove, install, remove.... repeat as neccessary until it works!!?? This is a pretty lame solution. Why can't they just hurry up and make a Vista friendly patch? It would seem like a relatively simple thing to do. Like it or not, Vista is here to stay, everybody knew it was coming. There is no excuse for the lack of support.
I like Vista so far, IMO it is far superior to XP in every way. All my favorite games run fine including SSIII (except that I can't get the damn patch to install). Another thing I noticed with the patch is that it says that it is updating it to v.1.3 not 1.4b... Is it a 2 part install? Either way it always fails before installing any patch at all.
