This application does not exist (app_id=xxx)
I fixed this problem by editing my app.yaml file to have the correct application name. In the app.yaml file where it says 'application:[insert app name here]', I had to change the [insert app name here] part. I'm not sure why the name was wrong, but I do remember toying around with it before while attempting to fix a different bug. The way I figured out the proper name was to go to my applications in my GAE admin console and look to see what the app's name was there. Hope this helps anyone else that runs into this same problem :)
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.