When I was developing a SharePoint 2013 app I encountered the following error when I published the App package and tried to add the App to a site:
The specified application identifier [GUID] is invalid or does not exist.
The problem seems to be that the App itself is not registered (as safe?) in the SharePoint tenant. In this case I use SharePoint Online. To fix that issue navigate to your App catalogue site collection and manually open this page: “_layouts/15/appregnew.aspx”
There you can register a new App with appropriate Client Id and Client Secret. Don’t forget to update your AppManifest.xml in your App and the Web.config when you are also using a seperate Web App project.