This application does not exist (app_id=xxx)
I got the same error message trying to make the first deployment of a Python Application using a Google Apps account.
In my case the problem was caused by the fact that my 2-way authentication is enabled.
With 2-way authentication enabled you need to generate an authentication password in your Google Account Management Application and use it to do the deployments.
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.