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 [1] (for now, I have added a mention to the superuser question [2] as a quick fix).

[1] http://wiki.musicbrainz.org/MusicBrainz_Server/Setup#MusicBrainz_Server_virtual_machine
[2] http://superuser.com/questions/90584/network-interface-missing-in-ubuntu-after-changing-mac-address