If you get a problem whereby newly created Office 365 users have not been synchronized to Dynamics CRM after you have assigned them a CRM licence then you should check the following.
In the Office 365 portal under the admin menu select the CRM option. From there select the “Edit Settings” for the CRM instance you are having problems with. Check that the “Instance Security Group” is not set otherwise only users in the assigned group will be allowed access to that CRM instance.