Ping Failed when creating new KVM machines

Whenever I create a KVM instance I get the "completed successfully" notification, yet ping always fails to the VM.

"KVM instance was started, but could not be accessed via SSH after 60 seconds"

I can access the created machine only via the console and not via ssh or web (locally or externally) - it is entirely invisible from the outside. Attempting to SSH into it gives me a 'password' prompt (so something is being reached), but it doesn't recognize passwords. When attempting to ping the VM (either via the IP address, or via FQDN), it just doesn't ping.

It seems it is working as the machine is obviously running ok and I can connect via console or remote VNC.

I really don't know where to start looking for config files - I am running cloudmin gpl.

If I do a ifconfig in the console, it initially (after creation) only gives me the IPv6 address. Then, if I manually configure IPv4, it shows both. The VM can reach the outside (albeit initial resolution is very slow). I can ping the gateway (the host machine or web addresses), but I can not ping other IP ranges that are installed on this machine

This systems worked well for the longest time, this has just started misbehaving a while back.

No idea what could be causing it.

Running CentOS 6.9, and uses br0 bride setup.

Harry