Ubuntu Servers :: Server 10.04, One Interface Not Brought Up On Boot?

I'm having an odd problem with Server 10.04. I have two interfaces but only one interface is brought up on boot - and it's not always the same interface. Usually eth0 fails and eth1 comes up fine, but sometimes eth1 fails and eth0 comes up. I'm using the same config that was previously used on Server 8.04, but never had this problem on 8.04.

/etc/network/interfaces:

Code:
# The loopback network interface
auto lo
iface lo inet loopback[code]....

Once the system has booted, if I run /etc/init.d/networking restart, then both interfaces come up fine. However, having read that this is now an upstart, I also tried service networking restart, but get:

Code:
restart: Unknown instance:
Don't know if that's significant or not.

Cannot find a single problem with networking reported in log files, other than bound services failing to start as a result of the interface not being up (dansguardian, squid, dhcp which are all bound to eth0, and therefore fail when eth0 doesn't come up. And when eth1 doesn't come up, the only process that fails to run is clamav-freshclam). Although at one point I did see something about interfaces being renamed which seemed a little odd.

I could just have networking restarted automatically once booted, but this obviously isn't a solution to whatever is causing the problem. There is quite a bit running on the server: Samba/LDAP domain controller with roaming profiles, squid & dansguardian with LDAP auth, postfix & dovecot with LDAP auth, mailscanner, dhcp & ddns, strict iptables policy with nat... so I'm not sure if any of those could have any bearing on interfaces?