[Users] Can't connect to any console

So, I've finally managed to set up an all-in-one setup on a CentOS box. Issue is, I can't connect to any running VMs, connecting to the console works. After some headaches, I've found that VNC just fails, while Spice says that there is no route to the host. Thinking it was just that it disregarded /etc/hosts, I setup dnsmasq. Still got issues. dig shows it resolves, tracepath shows a path and ping gets replies. (see <http://pastebin.com/raw.php?i=qWy8RnA6>) Have anyone here had similar issues? How did you do to fix it?