have you tried pinging the other computers from the server or vice versa? Might help narrow down the problems such as any hardware faults.
Are the desktops set as members of a workgroup? If so you may have to change them to the domain that the server is set as.
Have you tried accessing the server from one of the desktops by typing this into windows explorer:
that should get you into it even if they can't see each other due to different domains/workgroups.
Sorry for the random thoughts but I have only limited experience with windows networks/servers.