Make sure that the workgroup name on the client machines have the same workgroup name as the domain name just leave off the suffix. (mydomain.lan would be workgroup name mydomain).
You said you can ping the server. Make sure that you can ping the server by IP as well as HostName. If the first works and the second fails, then your netbios information is not being propagated across the network and you should tend to that. Make sure that the server has a fixed (static) ip address. From the client machines open command prompt and clear netbios name table cache
type nbtstat -R
then ping the server by ip and hostname
check the cache table on the client machine, command prompt type, nbtstat -c
if the server name and ip aren't in the client machines local cache then you have an issue.
You need a means of name resolution, eithere NetBIOS broadcast, WINS or DNS, don't know why you are not connecting to the domain, buy if this is going to be a long term process you might want to throw WINS on the server and point all the clients there under the WINS tab, in the IPv4 properties of each clients network card.
Also double check username and passwords, you say you have one user with two machines who seems to be able to attach to the server, is he using the same username and password on both machines?