Don't expect anyone to be able to help me, but.. I can try my luck!
So.. On my Linux system, I click Play, click Get New List, at which point I get an up-to-date list, then try to join a server... It says "Awaiting gamestate", then it just sits there... nothing happens unless I exit with ESC. I disabled the firewall, still nothing. After I press ESC and check the server's info, I can see my name in there.. and if I try to connect again to the same server, it says I'm already connected, and throws me out.
On Windows, everything works perfectly. I can connect to any Internet server.
On Linux, creating a server and playing, works. Creating a dedicated server and connecting to it, works. Creating a dedicated server on another computer (different LAN, too) and connecting to it, works.
I then created a dedicated server on another remote computer, making sure I can reach it ONLY through my internet network interface, and made it public. I saw the name in the list, I tried connecting to it, and, to my surprise, it WORKED.
ANY other server except mine still didn't. Any suggestions on what else I could try?