Thanks for your reply.
Yes, the server is running and accepting remote connections. Ping works.
Just tried the following.
tsql -S <server-ip> - U <user>
And then typed in the password. That worked. So, suspecting it could be an ODBC issues or something to do with the sqlcmd. Probably...