[Users] Can't connect to any console

[Chloride Cull]

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?