Sounds like you need to uninstall and reinstall Client for Microsoft Networking.
Network Connections | Right click: Your Connection | Properties | General
tab | Install button | Highlight: Client | Add button | Highlight: Client
for Microsoft Networks | OK | Close
but before you do this, you might want to make sure that netlogon services is set to automatic in Services first. Same place that you are restarting the service.
Cheers!