Looks like there is some problem with the Domain which the VM was connected to. Tried creating a new user in AD and used the new user to Invoke-VM script but the new user also was getting the same error. Invoke-VM script was working fine with local admin. So switched to different AD, and now Invoke-VM script started working fine on the same VM.
There must have been some change to DC, but not sure what that is (tried comparing both the domains with gpresult but there was lot of differences so didn't proceed with the analysis).
We were still not able to find the root cause for this issue, but I'm not blocked anymore.
Thank you LucD for your help.
Btw, when I experience an AD authentication issue, I most of the time start with checking the secure channel (see the Test-ComputerSecureChannel cmdlet).
Thank you @LucD for the tip, will use it incase if I come across this issue again.