I'm seeing this problem with both the virtio and e1000 driver with both linux and windows guests. About 5 - 10% of the VMs I launch have network problems.
Interestingly, if I restrict the host machine to only ever allow one VM, the network problems go away completely. I just launched 75 VMs (one after another) and none of them had a problems. It's only if there are multiple VMs. Specifically, the network problems seem to occur when another VM is being launched. Maybe something is happening with the virtual bridge?
.:. jeremy