This application does not exist (app_id=xxx)

You have to log in in your gae account and create an application before you upload it, and your app_id has to have the same name as you app. You can't just upload it.

So go here, create your app, for example "example_app" and set the app_id=example_app and everything should work :)

The fix I found was to add the parameter --no_cookies:

appcfg.py update --no_cookies MyProjectDirectory/

This can happen when you upload AppEngine applications from different Google accounts on the same computer.

The same problem occurs with the Java/Eclipse plugin version of App Engine. The 404 happens when you're logged in to the wrong Google account from within the plugin. In that case, look at the bottom-left of Eclipse to see what account you're currently using.

Regarding the Python command line updater, if your cookies indicate that you're logged in to a Google account that doesn't have access to the application you're updating, then that would explain why ignoring those cookies by using "appcfg.py update --nocookies" fixes it.