Hi @Glenn Maxwell ,
I tried to test in my environment and can reproduce what you described.
So, I looked up the documentation and I found out that this is an expected behavior. The user parameter mail-enabled security principals (mail-enabled accounts or groups that have security identifiers or SIDs that can have permissions assigned to them), so the shared mailbox type is not supported.
Please refer to the following documents.
In your situation, if you do want to make it work, you can consider converting the shared mailbox to a regular user mailbox.
Here's a similar post for reference:
O365 Add-MailboxFolderPermission Error - user not valid
(Please Note: Since the web site is not hosted by Microsoft, the link may change without notice. Microsoft does not guarantee the accuracy of this information.)
Best regards
Shaofan
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.