Looks like someone modified the default role assignments in your tenant? Run the following cmdlet:
Get-ManagementRole -Cmdlet Set-Mailbox -CmdletParameters RecipientLimits
This will return all the Roles that contain set cmdlet/parameter combo. Make sure your users is assigned (directly or via Role Group) to at least one of them. Then, restart PowerShell and try again.