I create a base Ubuntu-10.04-x86_64 box, and do an "apt-get update" on it. Now I want to use it to create clones for client development boxes. VirtualBox 4.1's "Clone" feature makes this easy. Before you shutdown this base box that you'll clone, do this:
sudo rm /etc/udev/rules.d/70-persistent-net.rules
This causes the clone to not have any persistent information about its network interface, so when it boots, it will generate a new config to match the MAC address it finds as it's booting. This is the critical part.
Now shutdown your base box and use the "Clone..." command.
Give the box a new name and be sure to click the "Reinitialize the MAC address of all network cards". You need unique MACs so to prevent conflict if you run more than one clone at a time. When the machine boots, it won't have any 70-persistent-net.rules so it will regenerate it with its new MAC address, just like we want.
The next screen lets you pick "Full Clone" or "Linked Clone" and the latter uses MUCH less disk space than the former. I believe it links the new VM to a snapshot of the base you previously created. Building a Linked Clone is much faster than a Full Clone.
Boot the box and login, and you should see your new interface (e.g., eth0). If you don't, double check the base box's 70-persistent-net.rules. You can always simply remove it on the clone and reboot and get a new one, and you'll be good to go.