Why not just set up your ubuntu server to be a dns and dhcp server and not worry about zeroconf? First, configure the dhcp server to give out addresses in some range sufficient for your needs. Then, set up a forwarding nameserver on the machine. These instructions are pretty similar to what you want to do. Basically you are allowing the dhcp server to change your dns server on the fly. Then when the other virtual machines on the network come up, they send their preconfigured names to the dhcp server. The dhcp server in turn sets those names in dns for your local domain.
Another very simple option is to set up something like DNSmasq. DNSmasq can read the server's /etc/hosts file and serve those entries up via dns to other machines on your network. So in this scenario you would maintain a big hosts file on the server of all the VM names, and the machine would again automatically serve those names over dns. You would still want to use dhcp in this case so the VMs could get addresses on your network automatically, but this is a simpler approach than configuring BIND for dns.
My suspicion is that dhcp + dnsmasq will probably work for you, unless you are attempting to run massive numbers of VMs.
