This week I had a migration from local to Office 365.
This tenant was earlier used for testing purposes, all users are synced with AADConnect to the tenant. When I tried to add a license to this user, I received an error, I’ve never seen before; “Uniqueness constraint violation”.

Error while adding license to a User:

This is the error : Uniqueness constraint violation

Solution:

Go to the Exchange admin Center, and remove the present contact with the same email address, and try to add the license again.

There is also a posibility the contact is also sync, so check this also in your local AD.

The licenses can be added now.