I’ve seen a number of people posting about this issue on forums and in blogs, and the resolution tends to be to change the version number or the client ID and redeploy.  That approach will work, but it’s a bit of a hack.  Here is another option to try before going that route:

1. Delete the app
2. Delete the app from the recycle bin
3. Delete the app from the second-stage recycle bin

Every time I have encountered this problem, making sure the app is completely deleted before attempting to add it back to the site seems to work.  I think there is just something behind the scenes in the app model that really doesn’t work well with the recycle bin concept.