This application does not exist (app_id=xxx)
Posting Ric Moore's comment in the selected answer because that is a valid answer and it worked in my case (and hopefully it helps someone else having the same issue spot it quickly).   

I have an alternation solution - in the Google App Engine Launcher select from the menu Control > Clear Deployment Credential. Then when you click Deploy it will take you through the auth flow again and you can select the correct account. - Ric Moore
I was unable to upload to an AppEngine as appcfg was telling me :

This application does not exist (app_id=u'xxx').

I was only a developer on the AppEngine, so as I was just testing I created a new AppEngine where I was the owner but I still get the same message on a newly created AppEngine.