Let's start from the assumption that we are the administrator on VS Online. We added a user a few days ago on our project, with the same rights like other users. Even if we added the user, he is not able to access our project. It is well known that sometimes we need to wait a few hours until the rights and changes are propagated, but it never takes more than 12-24h.
In this moment we need to ask yourself what is different. There are times when the change propagation freeze and you need to remove and add the user again. We sad that this might be possible and let's remove the user and add him again to VS Online and to our project.
After removing the user we observed that we cannot find anymore the given account, even if it was a LIVE account. This was strange and odd. We remembered that a few days ago we had a similar issue (http://vunvulearadu.blogspot.ro/2015/12/visual-studio-online-administrators.html) because the integration between Azure AD and company AD.
We added the LIVE account to our AD as member. After this we added again the user to VS Online and project group.
New-MsolUser -UserPrincipalName firstname.lastname@example.org -DisplayName "User A B" -FirstName "User A" -LastName "B" Set-MsolUser -UserPrincipalName email@example.com -UserType Member
Surprise, everything works as expected. The lesson learn is to double check the users in AD especially when under that subscription you have integration between on-premises AD and Azure AD.
Below you can find an MSND link where you can find the list of PowerShell comands that can be used in situations like this.