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.