Ubuntu - Microsoft SQLCMD - Error Locating Server/Instance Specified

So, I have this issue that I can't connect to an MS SQL Server from an Ubuntu VM. The situation: - One Windows Server with multiple MS SQL Instances - Two Ubuntu 20.04 LTS VMs One of the two Ubuntu VMs was perfectly able to connect to the SQL server using

sqlcmd -S sqserver.example.com\\instance1 -U sql.serviceaccount -P 'mypassword'

` but on the other server (which is very similar in setup, same network, ubuntu version etc) I get the following error

Sqlcmd: Error: Microsoft ODBC Driver 17 for SQL Server : Login timeout expired.
Sqlcmd: Error: Microsoft ODBC Driver 17 for SQL Server : MAX_PROVS: Error Locating Server/Instance Specified [xFFFFFFFF]. .
Sqlcmd: Error: Microsoft ODBC Driver 17 for SQL Server : A network-related or instance-specific error has occurred while establishing a connection to SQL Server. Server is not found or not accessible. Check if instance name is correct and if SQL Server is configured to allow remote connections. For more information see SQL Server Books Online..

So, I began to trouble shoot on VM2: - I can ping sqserver.example.com - Using nc I can connect to the open port of the SQL instance (something like port 56042) - Removed every firewall rule and allowed all traffic using iptables` - Rebooted the VM - Checked the IP config (which is like the VM1 where it does work, only the IP address is one higher, 172.16.1.12 instead of 172.16.1.11). - Checked the ARP tables on both ends, making sure there was nothing funky there (no duplicate IPs or something) On the SQL side: - Double checked that the SQL Browser Service was running (and restarted it) - Restarted the SQL instance` - Checked if there was a Windows Firewall (there isn't one enabled). Having done all that I gave up and reinstalled Ubuntu on VM2. Default server install, nothing special. Installed the Microsoft SQL tools on the same manner as before (and as on the VM01). Of course I sort of hoped it would work but to my suprise and chagerin I get the following:

Sqlcmd: Error: Microsoft ODBC Driver 17 for SQL Server : Login timeout expired.
Sqlcmd: Error: Microsoft ODBC Driver 17 for SQL Server : MAX_PROVS: Error Locating Server/Instance Specified [xFFFFFFFF]. .
Sqlcmd: Error: Microsoft ODBC Driver 17 for SQL Server : A network-related or instance-specific error has occurred while establishing a connection to SQL Server. Server is not found or not accessible. Check if instance name is correct and if SQL Server is configured to allow remote connections. For more information see SQL Server Books Online..
r

Exactly the same error. Besides that I can ping the SQL server I can also download files from a webserver on that machine using curl to the VM02. I am a bit out of options. The SQL server is reachable by another Linux machine and several Windows machines. ---------- Update: Using this piece of Python script I discovered I just don't get a answer from the SQL browsers service. On VM1 I get the following response:

Instance 172.16.1.123\instance1 is listening on port 56044.

On VM2 I get the following response:

No response from the SQL Browser service. Verify that the service is available on 172.16.1.123 and \instance1 is a valid instance name on it.

Of course, both running with the same script. ---------- Update: So I can connect to a specific instance using

sqlcmd -S tcp:sqlserver.example.com,56040 -U sqlaccount

So this work, still very strange but I'll take it for the moment.