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.

[…]