I had one VM in my VirtualBox and wanted to use it as a template/image so I cloned it. Then I launched both the original and the clone simultaneously (to simulate a server cluster for something I was working on), however, both instances were assigned the same IP address. Is this perhaps a bug in our DHCP, which I think VirtualBox uses to get IP addresses? Or perhaps something in the way I set up my VMs? Anyway, I am ultimately interested in resolving this issue so that I can two VMs of the same image concurrently.
This is known as an IP conflict and can cause major headaches on the network.
You can re-initialize the MAC address of the cloned VM; that just means generate a new random one. On your cloned VM click Settings >> Network >> Advanced then click the two circular arrows to generate a new MAC. Your VM will need to be off. When it boots your DHCP server should assign the VM a different IP address.
Also FYI, when you cloned your VM you should have seen a checkbox with the words "reinitialize MAC", that would have cloned the VM and generated a new MAC instead of cloning it.
If you were curious, cloning a VM is often used to make a full backup of the VM, in this case you would want the MAC and IP to be the same in case you had to use the backup. For your case of cloning the VM to build a cluster you'll want to re-initialize the MAC on every clone.
Update 1 In response to your comments from 10/8/2013.
Make sure the IP address is not statically set. You mentioned in your question that the VM should be getting it's IP from DHCP. If thats the case the config should look something like the following. For debian based systems it will be found at /etc/network/interfaces
For redhat based systems the networking configuration is at /etc/sysconfig/network-scripts/ifcfg-eth0
Your second comment mentioned that eth0 is missing. Do you have an eth1? Since your computer changed mac addresses, the OS keeps the original mac as eth0 and usually assigns eth1 to the new mac. To reset the eth* devices so you have an eth0 and not an eth1 you'll need to clear the udev networking rules.
Messing with networking can get hairy. One option would be to delete your cloned VM and clone the original again and check "reinitialize mac". I'm not certain it will fix your problem but it might.