If you are still running WINS (I do for simplicity) and have two NICs in your WINS box, you will need to change the order of the NICs so WINS knows where to look. This was driving me nuts.
Things I did to resolve the issue.
DNS Server, on the Interfaces tab disable the NIC your non "main" NICs.
NIC, Under "Manage Network Connections" select your non "main' NIC, uncheck all boxes except for IPv4/6. Then select your IPv4 box, uncheck register DNS, and disable NetBIOS.
Still in the Manage Network Connections, select Advanced (File Menu) -> Advanced Settings. Move your "main" connection to the top of the list. Press ok.
You are done, go back and WINS should know be able to resolve/connect.