This error took me quite a long to figure out, so I thought to write this down so I might remember this the next time I encounter the same error.
My situation was that I was able to connect to an on-prem MS SQL server through a newly created Azure VM, but when publishing a report to the Power BI service and by using a gateway connection, the connection attempt was not successful.
The reason for this was that on Power BI Desktop, I had defined the SQL server URL to use a port with colon :443. And it seems that Power BI service gateway connections do not support colon :.
This was indeed quite tricky to figure out, even though the fix is super easy. Just change the server connection on Power BI Desktop to use a comma instead of : (ie. serverurl,443 instead of serverurl:443).
To summarize, never use a colon, use a comma for db port settings.
Hopefully, this will help someone someday.