UWP app can't be updated after new certificate

Our UWP app recently got a updated certificate (pfx). New users are able to install it, but users with previous versions cannot update.

When they try to update they get the message:

Ask the developer for a new app package. This package may conflict with a package that is already installed or it may depend on things not installed here (package dependencies) or be made for a different architecture (0x80073CF3)

A workaround to this is to uninstall it and reinstall it, but group policy for our customer prevents this. Is there a way of updating without uninstalling?

The package family name (subject) is different in the new licence.

When installing via Powershell:

Windows cannot install package *******_12.1.0.0_neutral_~_83zx72fh7sqme because a different package *******_13.2.1.0_x86__e91qp94tx8r3y with the same name is already installed. Remove package *******_13.2.1.0_x86__e91qp94tx8r3y before installing.

UPDATE We got a certificate from a different provider with EXACTLY the same subject and are able to update the app rather than reinstall it.