Comment 3 for bug 345234

I found this thread on the Ubuntu forums that also discusses this problem (in combination with VMware, but that's beside the point, since this happens whenever an ubuntu/debian system is cloned): http://ubuntuforums.org/showthread.php?t=1045715

There are several solutions to this bug:
- Simply delete /etc/udev/rules.d/70-persistent-net.rules either before or after the cloning, or edit the file after cloning.
- Remove execute permissions from /lib//udev/write_net_rules, but that results in an error on startup
- Edit /lib/udev/rules.d/75-persistent-net-generator.rules so that it ignores MAC addresses from VMware or KVM. For Xen such a line already exists:
# ignore Xen virtual interfaces
SUBSYSTEMS=="xen", GOTO="persistent_net_generator_end"

From the forum post above, add the following for VMware
# ignore VMware network interfaces identified by vendor part of MAC addr
ENV{MATCHADDR}=="00:0c:29:*", GOTO="persistent_net_generator_end"

For KVM and virt-clone I added these:
# ignore KVM virtual interfaces
ENV{MATCHADDR}=="52:54:00:*", GOTO="persistent_net_generator_end"
# This eems to be the range used by Xen, but also by virt-clone
ENV{MATCHADDR}=="00:16:36:*", GOTO="persistent_net_generator_end"

Make sure these lines are after the following lines:
# read MAC address
ENV{MATCHADDR}="$attr{address}"

This worked for me.