I had the same problem with some machines. Always the problem was a bad installation of the network card drivers. You could see if this is the problem in the control pane ->system, a yellow or red exclamation icon will appear in the network card.

Always until one month ago...

I installed a new network card in a computer. The first time I restarted the computer, the computer doesn't asked me for the microsoft network user but yes for the standard windows user. The next time I restarted the computer, it doesn't asked me neither for the net user, nor for the windows user. But that computer could be seen by the entiere network with the name I gave the first time (the windows user). And that computer couldn't see the others computer of the network.