Invalid computer name error with remote execution of PowerShell script

I am trying to execute some PowerShell code in a remote computer using the following:

$session = New-PSSession -Credential "myDomain\myUserName" -ComputerName "remoteCompName"
$result = Invoke-Command -Session $session -ScriptBlock {
    New-Item -type file C:\test10.txt
}

I am prompted to enter my password in a GUI. I do that. It then errors out with:

New-PSSession : One or more computer names are not valid. If you are trying to pass a URI, use the -ConnectionUri parameter, or pass URI objects instead of strings.

I replaced the computer name with the FQDN. Still no luck. What is going on here?

There are other questions on stackoverflow on executing PowerShell scripts on remote machines of course but none address this error.

BTW, the machine is part of the domain and is running.

Additional info added later [EDIT]

Things to know:

1. The machine is part of the domain and is running.
2. I checked if PS remoting is enabled. It was.
3. I checked if WinRM is running. It is.
4. The remote machine is a VM and it is a 2012 R2.

Here is what I've tried:

1. I replaced the computer name with the FQDN. Still no luck.
2. I removed the credential parameter
3. I tried another remote machine (also a VM)
4. I tried another source machine, i.e. the machine I am running the command from)

Thanks!

-Rohan.