I tried that but we weren't really having the same problem (I didn't have 200 of the network adapter he was referring to, I still removed all the network adapters and restarted to reinstall. Unfortunately it didnt help. I also tried:
* disabled and reenabled network browsing for the 'home' and 'public' profiles
* this:
PeteNetLive - KB0000439 - Error - While Attempting to Access a Windows Share
*enable NetBIOS always on in the TCPIP settings
*restart the winbind/smbd/nmbd services on the samba box
*disable the firewall again
*reboot the router
*Enabling the 'router' service
*Making sure the following services were enabled
COM+ Event System (for WZC issues)
Computer Browser
DHCP Client
DNS Client
Network Connections
Network Location Awareness
Remote Procedure Call (RPC)
Server
TCP/IP Netbios helper
Wireless Zero Configuration (XP wireless configurations)
WLAN AutoConfig (Vista wireless configurations)
Workstation
I'm afraid that this will require a clean install. I did have a problem mixing up the location on two computers and had problems removing the old settings before a restart, I wonder if I messed up the registry. Either this, or maybe its another case of impossible-to-diagnose-windows-problem (linux may be a real pain to setup, but there's always an error log to find out what's going on).