I have been getting this with Feisty, Hardy and Intrepid. The nic is not recognised at install time. It is an old isa ne2000. I add the module name and options to /etc/modules then configure /etc/network/interfaces to use dhcp. When the machine boots it has network connectivity. Like Tessa reported I have a problem with programs saying they are in offline mode even though the network is working.
iface eth0 inet dhcp
I uninstall network manager and no more problems.