No expected fix from Atlassian:

Our senior support engineers came to a conclusion that this is expected behaviour. Due to the high number of users on the instance, JIRA has to do a full sync with Crowd each time a user is changed, which takes 5-6 minutes, after which time the users can log in as normal. For now, due to the current structure of Crowd synchronization, I am afraid there is no workaround to the matter.
I can only suggest that it is mentioned before hand that it may take some time before the newly created users can login.