For those googling, above error happened for us when trying to use application-based authentication for the MS Teams PowerShell commandlets.

We followed the instructions but kept getting Invalid credential Provide valid credential whenever calling a cmdlet, while the connect-microsoftteams command worked fine with the -accesstokens param.

Turns out, when you assign application level permissions to your service principal on top of the delegated permissions, the SPN is not authorized for all subsequent cmdlet calls :O