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.
That's interesting, I've never had to open any ports on any wallet I've ever used. Is your network double NAT'ed? Behind two firewall/routers by chance? One other thing you can verify is that you have the most update .conf file which has the most updated nodes. You can find that here:
http://resources.vericoin.info/category/technical-support-files/