android App installation failure "Installation error code: -25" on Galaxy S4

I had problems when I was trying to install a new version of our app.

There was no problem installing the app on its own,
but if the previous version of the app (from google play) was installed it just refused to install the new version over it.

The installation would just say "App not installed" and logcat would say  "Installation error code: -25".

Eventually it turned out that some changes I made to our build process change the versionCode to a lower number then that of the version that was available on google play.

Bumping the version code up resolved the issue.