What do you mean by "connect?" What kind of "connection?"
Are you losing a mounted share? Are you unable to authenticate via Active Directory?
"Connect" is very vague... there are hundreds of "connections" a client computer can make to a server -- accessing a shared printer, viewing files stored on a mounted share, authenticating with a directory service, etc. Since you can ping each machine from the other, right there you have a "connection" that is working -- the physical ethernet cable is "connected," and you are able to communicate via TCP/IP (because you can ping the machine).
What specific action were you trying to accomplish on the Mac when you got this message? Mount a shared drive? Access a printer? Was the Mac set up to auto-mount a shared drive upon login, and perhaps it can't find that share anymore?...and attempts to reconnect via "Finder" get a message "Conncetion failed."