Back in November 2006 I installed the RTM version of Vista - and then found that all of my Microsoft games (such as Age of Empires III and Rise of Nations) no longer played. I then spent a lot of time with Microsoft tech support agents, who ranged from helpful to not even remotely helpful - thanks, oh random Indian call center employee, who decided that this could not possibly be a Vista error and transferred me to a line that I let ring for half an hour before hanging up.
Then, a little bird suggested I turn off DEP.
The games work now.
Moral of the story: If you're trying to play a game on Vista and you get the "Protection Stub has stopped working" error, try turning off DEP, rebooting the computer, and starting the game again. Apparently it's something to do with an incompatiblity with the Macrovision SafeDisc copy protection scheme, but who really knows for sure?