on 12.04 this annoyance still exists - debian package has updated
/lib/udev/rules.d/75-persistent-net-generator.rules with virtualbox-
friendly rules - please copy and paste from e.g.
http://packages.qa.debian.org/u/udev.html
# These rules generate rules to keep network interface names unchanged
# across reboots and write them to /etc/udev/rules.d/70-persistent-net.rules.
# variables used to communicate:
# MATCHADDR MAC address used for the match
# MATCHID bus_id used for the match
# MATCHDRVdriver name used for the match
# MATCHIFTYPE interface type match
# COMMENT comment to add to the generated rule
# INTERFACE_NAME requested name supplied by external tool
# INTERFACE_NEW new interface name returned by rule writer
ACTION!="add", GOTO="persistent_net_generator_end"
SUBSYSTEM!="net", GOTO="persistent_net_generator_end"
# ignore the interface if a name has already been set
NAME=="?*", GOTO="persistent_net_generator_end"
# device name whitelist
KERNEL!="eth*|ath*|wlan*[0-9]|msh*|ra*|sta*|ctc*|lcs*|hsi*", \
GOTO="persistent_net_generator_end"
# ignore Xen virtual interfaces
SUBSYSTEMS=="xen", GOTO="persistent_net_generator_end"
# ignore UML virtual interfaces
DRIVERS=="uml-netdev", GOTO="persistent_net_generator_end"
# ignore "secondary" raw interfaces of the madwifi driver
KERNEL=="ath*", ATTRS{type}=="802", GOTO="persistent_net_generator_end"
# ignore "secondary" monitor interfaces of mac80211 drivers
KERNEL=="wlan*", ATTRS{type}=="803",GOTO="persistent_net_generator_end"
# by default match on the MAC address and interface type
ENV{MATCHADDR}="$attr{address}"
ENV{MATCHIFTYPE}="$attr{type}"
# match interface dev_id
ATTR{dev_id}=="?*", ENV{MATCHDEVID}="$attr{dev_id}"
# These vendors are known to violate the local MAC address assignment scheme
# Interlan, DEC (UNIBUS or QBUS), Apollo, Cisco, Racal-Datacom
ENV{MATCHADDR}=="02:07:01:*", GOTO="globally_administered_whitelist"
# 3Com
ENV{MATCHADDR}=="02:60:60:*", GOTO="globally_administered_whitelist"
# 3Com IBM PC; Imagen; Valid; Cisco; Apple
ENV{MATCHADDR}=="02:60:8c:*", GOTO="globally_administered_whitelist"
# Intel
ENV{MATCHADDR}=="02:a0:c9:*", GOTO="globally_administered_whitelist"
# Olivetti
ENV{MATCHADDR}=="02:aa:3c:*", GOTO="globally_administered_whitelist"
# CMC Masscomp; Silicon Graphics; Prime EXL
ENV{MATCHADDR}=="02:cf:1f:*", GOTO="globally_administered_whitelist"
# Prominet Corporation Gigabit Ethernet Switch
ENV{MATCHADDR}=="02:e0:3b:*", GOTO="globally_administered_whitelist"
# BTI (Bus-Tech, Inc.) IBM Mainframes
ENV{MATCHADDR}=="02:e6:d3:*", GOTO="globally_administered_whitelist"
# Novell 2000
ENV{MATCHADDR}=="52:54:4c:*", GOTO="globally_administered_whitelist"
# Realtec
ENV{MATCHADDR}=="52:54:ab:*", GOTO="globally_administered_whitelist"
# Kingston Technologies
ENV{MATCHADDR}=="e2:0c:0f:*", GOTO="globally_administered_whitelist"
# ignore interfaces with locally administered or null MAC addresses
# and VMWare, Hyper-V, KVM, Virtualbox and Xen virtual interfaces
ENV{MATCHADDR}=="?[2367abef]:*",ENV{MATCHADDR}=""
ENV{MATCHADDR}=="00:00:00:00:00:00",ENV{MATCHADDR}=""
ENV{MATCHADDR}=="00:0c:29:*|00:50:56:*|00:05:69:*|00:1C:14:*", \
ENV{MATCHADDR}=""
ENV{MATCHADDR}=="00:15:5d:*", ENV{MATCHADDR}=""
ENV{MATCHADDR}=="52:54:00:*|54:52:00:*", ENV{MATCHADDR}=""
ENV{MATCHADDR}=="08:00:27:*", ENV{MATCHADDR}=""
ENV{MATCHADDR}=="00:16:3e:*", ENV{MATCHADDR}=""
LABEL="globally_administered_whitelist"
# ibmveth interfaces have stable locally administered MAC addresses
SUBSYSTEMS=="ibmveth", ENV{MATCHADDR}="$attr{address}"
# S/390 interfaces are matched only by id
SUBSYSTEMS=="ccwgroup", \
ENV{MATCHDRV}="$driver", ENV{MATCHID}="$id", \
ENV{MATCHADDR}="", ENV{MATCHDEVID}=""
# terminate processing if there are not enough conditions to create a rule
ENV{MATCHADDR}=="", ENV{MATCHID}=="", ENV{INTERFACE_NAME}=="", \
GOTO="persistent_net_generator_end"
# provide nice comments for the generated rules
SUBSYSTEMS=="pci", \
ENV{COMMENT}="PCI device $attr{vendor}:$attr{device}"
SUBSYSTEMS=="pcmcia", \
ENV{COMMENT}="PCMCIA device $attr{card_id}:$attr{manf_id}"
SUBSYSTEMS=="usb", \
ENV{COMMENT}="USB device 0x$attr{idVendor}:0x$attr{idProduct}"
SUBSYSTEMS=="ccwgroup", \
ENV{COMMENT}="S/390 device at $id"
SUBSYSTEMS=="ibmveth", \
ENV{COMMENT}="LPAR virtual device at $id"
SUBSYSTEMS=="ieee1394", \
ENV{COMMENT}="Firewire device $attr{host_id}"
ENV{COMMENT}=="", \
ENV{COMMENT}="Unknown $env{SUBSYSTEM} device ($env{DEVPATH})"
ATTRS{driver}=="?*", \
ENV{COMMENT}="$env{COMMENT} ($attr{driver})"
# ignore interfaces without a driver link like bridges and VLANs, otherwise
# g
