If you are here you probably had the issue from the title the error INSTALL_FAILED_UID_CHANGED when you want to install for debug the app from Eclipse or Android Studio.
I had this issue yesterday and after hours of browsing the stackoverflow and groups and forums I found 3 methods to fix this.
1. if you test on an emulator then you just have to Clear/Wipe the AVD to defaults or create a new one.
2. you are on a real device. If you have root access to the device just go to folder
and delete it. You should ok now.
3. Device with no ROOT Access. On internet there is just one single method to factory reset the device. If this is acceptable for you this is easy.
None of this methods was OK for me. I was testing on a real device with NO-ROOT but I did not want to factory reset it.
My luck was to use GIT git as version control and to commit changes after every successful debug install.
So to fix the error INSTALL_FAILED_UID_CHANGED i did revert the source code to the last commit it worked. Push the build to the device and the install was successful. After this I did uninstalled the app from device (Settings->Application) and push the app from Android Studio with the lasted source.
In conclusion the error is happening when not all files are deleted before app reinstall. Before having this error I did renamed a module in my source code and modified the manifest. And some other small code changes. So I do not exactly know witch changed the UID but reverting to the last source code that I know it worked manage to fix my device without ROOT.