The error message "some nodes were not ready" is somewhat misguiding, as it seems that the reason was having two other nodes in the cluster up and running but configured to still use the AllowAllAuthenticator. After bringing down the other nodes and starting up the one with PasswordAuthentitor, creating default user succeeds:
INFO [NonPeriodicTasks:1] 2013-10-09 14:44:57,028 PasswordAuthenticator.java (line 237) PasswordAuthenticator created default user 'cassandra'
INFO [NonPeriodicTasks:1] 2013-10-09 14:44:57,760 Auth.java (line 218) Created default superuser 'cassandra'