This application does not exist (app_id=xxx)
This is really old, so I wouldn't be surprised if this isn't picked up by the poster, but I wanted to ensure that I have a reference for the next time I have the issue.
I had this issue. My problem ended up being that I had not invited the user that I was authenticating as to be a developer on the project. In fact I had just created the user and not even logged on yet.
I logged on to the google infrastructure as the new user, then added the new user as a developer on the application. I was then able to upload the app.
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.