By default, linux assigns eth0, eth1, etc.. to a specific mac address. If the mac address of the machine changes it may bring up the network card under a new name, or not at all. The fix in this case is to remove all the remembered mac addresses with:
sudo rm /etc/udev/rules.d/70-persistent-net.rules
This isn't mentioned in the documentation, and many users who come to our irc channel because of problems with the virtual machine image turn out to have this problem.
A possible solution is to either disable this feature in some way (remembering mac addresses), I do not know if that is possible on current linux distributions. Alternatively, perhaps we can ship the virtual machine with this file removed -- so that the file is recreated on first boot-up by the end user. A suboptimal or interim solution would be to document this behavior in the installation instructions on the wiki  (for now, I have added a mention to the superuser question  as a quick fix).