ClickOnce deployment "Activation failed" FileNotFoundException

I just deployed an update to a clickonce application. I have deployed dozens of updates with no issue. Now all of a sudden, with this update, all my users are reporting this error:

ERROR SUMMARY

Below is a summary of the errors, details of these errors are listed later in the log.
    * Activation of C:\Users\XXX\AppData\Roaming\Microsoft\Windows\Start Menu\Programs\XXX\XXX\XXX.appref-ms| resulted in exception. Following failure messages were detected:
        + Activation failed.
        + The system cannot find the file specified. (Exception from HRESULT: 0x80070002)

Following errors were detected during this operation.

* [3/15/2012 3:22:34 PM] System.Deployment.Application.DeploymentException (Activation)
        - Activation failed.
        - Source: System.Deployment
        - Stack trace:
            at System.Deployment.Application.ComponentStore.ActivateApplication(DefinitionAppId appId, String activationParameter, Boolean useActivationParameter)
            at System.Deployment.Application.SubscriptionStore.ActivateApplication(DefinitionAppId appId, String activationParameter, Boolean useActivationParameter)
            at System.Deployment.Application.ApplicationActivator.Activate(DefinitionAppId appId, AssemblyManifest appManifest, String activationParameter, Boolean useActivationParameter)
            at System.Deployment.Application.ApplicationActivator.ProcessOrFollowShortcut(String shortcutFile, String& errorPageUrl, TempFile& deployFile)
            at System.Deployment.Application.ApplicationActivator.PerformDeploymentActivation(Uri activationUri, Boolean isShortcut, String textualSubId, String deploymentProviderUrlFromExtension, BrowserSettings browserSettings, String& errorPageUrl)
            at System.Deployment.Application.ApplicationActivator.ActivateDeploymentWorker(Object state)
        --- Inner Exception ---
        System.IO.FileNotFoundException
        - The system cannot find the file specified. (Exception from HRESULT: 0x80070002)
        - Source: System.Deployment
        - Stack trace:
            at System.Deployment.Application.NativeMethods.CorLaunchApplication(UInt32 hostType, String applicationFullName, Int32 manifestPathsCount, String[] manifestPaths, Int32 activationDataCount, String[] activationData, PROCESS_INFORMATION processInformation)
            at System.Deployment.Application.ComponentStore.ActivateApplication(DefinitionAppId appId, String activationParameter, Boolean useActivationParameter)

Of course it doesn't tell me exactly what file it's looking for that fails. I'm stumped on this!

At least a few people have been able to solve this by clearing out all of the ClickOnce data and reinstalling, blaming it on corrupt file storage.

See this MSDN forum post for more info.