Community Nickname has to be unique across all users? or it has to be unique within a org? As far as I know, username has to be unique across all Salesforce users in the world. Any thoughts?
Yes your salesforce username has to be globally unique. I would think the Community Nickname is only unique across your org.
You might also want to review this thread Handling Community Nickname field for Customer Portal registration