I ran into this problem on Debian Etch. If the vm only has one interface you can disable udev's interface cache by renaming the following rules:
/etc/udev/rules.d/z25_persistent-net.rules --> /etc/udev/rules.d/z25_persistent-net.rules.disabled
/etc/udev/rules.d/z45_persistent-net-generator.rules --> /etc/udev/rules.d/z45_persistent-net-generator.rules.disabled
The upside of this solution is that, as long as the vm only has one interface, it will always be named eth0, even if the mac address changes.
The downside is that you will probably have to use manually configured mac addresses if you want any reliability with multiple interfaces. But this is true in the case of the other suggested remedies also.