I started hitting this little gem of an error recently and was ready to pull out the little remaining hair I had, when a very kind Program Manager named Jim S. told me how to fix it. The scenario is something like this: you install an App for SharePoint in Office 365. You make some changes to the app that require you to remove and add the app again. So you go about doing that process of removing the app from the site, and then selecting and choosing to add it again. You even get the consent dialog asking you if you trust the app and you say okay. After that, things go a little sideways and you get an error that says Sorry, something went wrong…The provided App differs from another App with the same version and product ID. You look around and you don't see the app installed so it leaves you scratching your head.
If you search around on the interwebs you will find some posts that suggest you can fix this problem by increasing the version number of your application and reinstalling, and that will in fact allow you to add the app again. However, that is really not a solution, that is a work around. Well what Jim was good enough to point out is that the behavior for removing an app changed recently. Now, instead of actually removing the app from the site, it just puts it in the site's recycle bin. So the app really does live on, and that's why you can't add it again. The solution he suggested (and which I found to work) is to empty both the primary and secondary site collection. That removes the app completely from the site, and then you can add your application again. Whew!
One other thing to note - they've also recently modified the behavior again in Office 365 so that you should not hit this issue any more. When you are installing an app for the first time now, you can remove it and add it again many times and now it work successfully. However what I found is that for apps that were already installed, I had to go through the process described above to remove it from the recycle bin before I could add the app again. However once the app was completely cleared out of the site's recycle bins, after I added the app to the site again I no longer needed to clean out the recycle bin during this remove and add update process. So it looks like a little pain, but only until you get those apps cleaned out and added again.