So, making a hole in firewall for port 36988 (and forwarding it) did the trick, however as the program does not advertise that this is necessary and average user may not be tech-savyy enough to use netstat and figure out by itself ... then I see it as a quite an ugly flaw of the wallet.

Or, if they are behind NAT over they which has no control (ie. they can't set up any port forwarding) ... then they might be out of luck even if they know exactly what is the problem.

Most other coins can work quite well without the port forwarding (I can't remember of having to forward ports for any of the other coins actually ...), so this is what might be unexpected even to more advanced users.