I don't think it is the ne2k not bringing up it's carrier in time because it has always worked fine in F16 until the latest update to NetworkManager (NetworkManager-0.9.4-2.git20120403.fc16.i686). I also understand that NM should detect networks becoming available so if I physically unplug the network cable and then plug it back in, NM should detect this and bring networking up, it doesn't. Also looking at some log files from before the update, NM would report "Apr 22 13:09:18 trinity NetworkManager: <info> (p5p1): driver 'ne2k-pci' does not support carrier detection." but then go on to bring up networking. After the upgrade to the latest version it says:
Apr 26 19:21:57 trinity NetworkManager: <warn> (p5p1): couldn't get carrier state: (-1) unknown
Apr 26 19:21:57 trinity NetworkManager: <info> (p5p1): carrier now OFF (device state 20, deferring action for 4 seconds)
Apr 26 19:21:57 trinity NetworkManager: <info> (p5p1): preparing device.
Apr 26 19:21:57 trinity NetworkManager: <info> (p5p1): deactivating device (reason 'managed') 
I have filed a bug (816719) in the hope that the behaviour will be reverted to the previous version of NM. I have not downgraded NM in case extra info is required (and I can get networking going now - although a bit mandrolic). If you would like specific information, let me know.