Are you going through the web page to create your identifier first or just setting it in the app.yaml and attempting to upload? I had no problem setting mine up through the site first and then using the appcfg deal to up it.
It's weird, because I created an identifier with 4 letters and it worked, but only after my first choice identifier, also with 4 letters, didn't work and it said it wasn't avaiable.
I keep getting Application Identifier: App already exists. Even when I pick random App names. Odd.