When you uninstalled the NIC, did you put it back in the same slot? You can try putting it into a different one. You might also try changing the network name of the computer (read further to see why that isn't as stupid as it sounds).
This isn't an uncommon problem, and I haven't found anybody describing a way to really fix it. I recently had this happen on my laptop, after installing a mini-PCI wireless card to replace the previous one. If automatic IP addressing is disabled, you'll just get an "invalid IP address" or 0.0.0.0. The automatic IP address is Microsoft's idea, so that you can just plug computers into a hub and not need a server to assign IPs. Not a bad idea, but really probably gets little use.
What ended up fixing mine was that I bought a new wireless router (going from 11b to 11g), and immediately was able to connect and get an IP. Switched back to the 11b access point, no IP address. Back to 11g, works fine. I'm thinking that if I had just done something as simple as changing the SSID of the wireless network, Windows might have thought it was a "different" network and started working, just as it did with the new router. I didn't feel like trying it though, I'd rather not lose the connectivity now that I have it. Changing your network name may do the same thing.
If all else fails, network cards are very cheap, you can get them for 5 dollars or less (the no-name brands at a local PC shop, or computer show). Even the cheap ones provide decent performance and use the same chipsets as many brand name models.
