From what I understand, Linux uses bus numbering to determine the order of the interfaces and their numbering in a given machine. It can be PCI bus, mini-PCI or whatever else. Lately, due to the parallel startup scripts of all sorts and kinds, things have become outright random sometimes from one boot to another (actually, NICs have been more or less named the same on the same machine, but other devices not so much).
Obviosuly, the order of the devices on the bus changes from machine to machine. What doesn't change is the MAC address.
My solution:
If you are using udev, you can use the udev config rules similar to the ones described here (for Debin, ubuntu is similar) to force a binding between specific interface and the MAC address of the NIC.
Caveat Emptor: some NICs do allow to edit their MACs. In this case, it won't work.
Extra-curricular info: A harder-to-implement alternative would be to use the new mechanism Matt Domsch/Dell are proposing for Fedora, reviewed here
As far as Ubuntu goes, there is a proposal to integrate that scheme in as well. According to 1 above: Although Fedora is shipping biosdevname first, other Linux distributions are also expected to adopt it. There is reportedly a blueprint for integrating this in Ubuntu 11.04 already and a feature request for inclusion in OpenSUSE as well.
Hopefully this helps.