When opening the Address List on the Organization Configuration/Mailbox/Address List, you will notice the error:

The Specified address list could not be edited. Address lists created by using legacy versions of Microsoft Exchange must be upgraded by usng the "ForceUpgrade" parameter of the Set-AddressList cmdlet

This can be solved by using the Exchange Powershell and running the following commands:

Set-AddressList "All Users" -IncludedRecipients MailboxUsers
Set-AddressList "All Groups" -IncludedRecipients MailGroups
Set-AddressList "All Contacts" -IncludedRecipients MailContacts