Your syntax is correct. The issue is that you must use the FQDN of the server when you connect to it.
There are multiple things that do not work if you don't use the FQDN so I make it a habit to always use the FQDN when connecting.
So use Connect-VIServer -server FQDN.
Connect-VIServer -server FQDN
New-TagCategory 'testCategory'
New-Tag -Name 'testTag' -Category 'testCategory' -Description 'testDescription'
Get-VM 'testVM' | New-TagAssignment -Tag 'testTag'
Blog: https://powershell.house/