The solution file located at 'xxx.wsp' does not appear to be a valid upgrade

Scenario:
Recently I have encountered the following error when I tried to upgrade my solution.

Explanation:
Usually this error means either the feature scope has been changed.

There have been theories that addition of a new feature(s) may be a cause for the same, but I have not experienced that so far. Adding a new feature to an existing solution and upgrading the solution does not always throw errors but simply won't list the new feature that is added to the solution. In order to have the new feature shown up in the feature gallery, a redeploy of the solution is required usually.
A good friend of mine Sandeep Nahta has written a good blog post describing the same

Finally it has been found that the error was due to the missing safecontols declaration node in manifest file. As one of the features in our solution has been scoped for webapplication and no safecontols were defined

  <Assemblies>
    <Assembly Location="Assembly.dll" DeploymentTarget="GlobalAssemblyCache" />
  </Assemblies>

After modifying the manifest file like below, the error disappeared:

  <Assemblies>
    <Assembly Location="Assembly.dll" DeploymentTarget="GlobalAssemblyCache">
      <SafeControls>
        <SafeControl Assembly="Assemmbly info" TypeName="*" Safe="True" />
      </SafeControls>
    </Assembly>
  </Assemblies>

If no new feature has been added to the solution or if the scope has not been changed, it may not always be a very good idea to retract, delete, install and deploy the solution again as any web app scoped feature(s) that may be present in the solution would be deactivated due to the same and therefore have to be activated again.