How was the Linux server setup? Did you build the Linux server on the windows machine or the Linux machine?
EDIT: Can you also see if you have the same problems connecting with the Mac if you are connecting to a Windows-server rather than a Linux-server?