Microsoft Knowledge Base Article 814833 contains the following Symptoms:

When you try to restore your computer running Windows XP to a restoration point before you applied a patch or service pack, the application that you applied the patch to may reach an unusable state. When you try to repair, install, reinstall, or remove the application, you may receive the following error message:

"This patch package could not be opened. Verify that the patch package exists and that you can access it, or contact the application vendor to verify that this is a valid Windows Installer patch package."