INSTALL_FAILED_UID_CHANGED usually occurs due to improper installation/Uninstall . The only way to fix this problem on a non rooted phone is using the below technique [In some cases this might not work]

1. Try changing the package name of your GCM permission.

Suppose you have a package name of -> com.androidcodelab.sampleproject then change that to com.androidcodelab.somename and run.

What this does is, it completely searches for the package name and removes it incase of a conflict thus removing the cause of the failed UID error.

Ex :
Package name of existing project :

Package name of the project changed to :

Try to install – Volla it installs fine -> now rename it back to the actual package name and your application will now install properly.

If this doesn’t work then try renaming your package name i.e., applicationId under defaultConfig in your build.gradle file and again try the above method.

If this works/doesn’t work in your case, please let us know by commenting below, so that it would be helpful for other fellow android developers as well.