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.
I couldn't create the identifier from their web page, it looks like it needs to be at least 8 characters long.
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.