How to deploy an update of a windows 8 lob/enterprise-app?

I've just completed an update for an lob-app, but when I try to deploy it as an update I get the error ERROR_PACKAGE_ALREADY_EXISTS (0x80073CFB). When I searched for this error I found the following error details:

The provided package is already installed, and reinstallation of the package is blocked.

You may get this error if installing a package that is not bitwise identical to the package that is already installed. Note that the digital signature is also part of the package. Hence if a package is rebuilt or resigned, it is no longer bitwise identical to the previously installed package. Two possible options to fix this error are: (1) Increment the version number of the app, then rebuild and resign the package (2) Remove the old package for every user on the system before installing the new package.

(http://msdn.microsoft.com/en-us/library/windows/desktop/hh973484(v=vs.85).aspx)

Indeed the package was resigned and a new certificate was used but I even incremented the version number.

Is there another way to deploy an update without having to uninstall the previous version first? If I got it right, every change in the app code or even every change of the certificate will result in an different package. That seems to be logical for me. I even incremented the version number from 1.0.0.1 to 1.1.0.0, rebuild and resigned it. But this doesn't seam to be enough.. still getting the error_package_already_exists:((

The update works fine if the same certificate is used for signing the new version, which was used for signing the installed version. By using a different certificate you have to uninstall the previous version first.