We have resolved the problem.
Further the investigation of more machines revealed that some machines actually worked after the uninstall (but most didn't). Also, if we used a static IP on the machines that did break, we could talk on the network just fine. This explained why the TCPIP fixes didn't work, because the stack was never compromised. It was now just a DHCP problem.
I found an article here on Experts Exchange (
http://www.experts-exchange.com/Networking/Misc/Q_23243418.html) where the expert told the author to check the DHCP service started. Wait for it.... it WASN'T. I know you.. I know.. "wasn't that the first thing you checked?". Yes, I promise and it was started. When the NC was installed the service always started, when the NC was uninstalled, the service didn't. And since the first rule of troubleshooting is "what did you change?" I never went back to look until I read the article. Once I started the DHCP client on the "broken" machines everything started working (no other changes needed).
When I checked the properties of the DHCP Client service, the 'Startup Type' was BLANK! The NC was taking the initiative to start it for us and when it was uninstalled Windows didn't know what to do with it because of the missing setting. I changed the Startup Type to Automatic and I can install, uninstall, reboot all day long and everything works fine. I don't know how the entry got corrupted, but this same image was used throughout the organization. So, the fix is simply making sure the [DHCP Client service] > [Startup Type] is set to 'Automatic' before we uninstall.
I am the first person to turn my nose up at the Novell Client (AOL and the like) as they do so much you have to trust that they put everything back in its original state. In this case the NC was FIXING a problem we didn't know we had. So if I sparked any negative conversations towards the NC, in this case, it is unfounded.
I guess the moral here is: sometimes it really is something simple!
Thanks for everyone's help!
