Your computer could not connect to another console session on the remote computer because you already have a console session in progress.
Dumb Fix:
Use the IP Address instead of the name to connect. You can get the IP address using ipconfig on the remote device or by using ping with the computer (or domain) name.
Instead of
Computer: RemoteComputer
User Name: AdminGuy
Computer: 192.168.1.23
User Name: AdminGuy
Note that the above fix only works in certain instances where DNS is on the fritz. As usual it is a horrible message not much better than 'error'.