It works for me on Windows as well, but not much on Debian either.
Maybe you didn't supply a username when connecting with Nautilus? Put Tomcat CIFS server into debug mode and check the logs (catalina.out).
When I give a username, I'm then prompted for a password and after being authenticated (displayed in the logs) I have access to the root of the network share (Alfresco directory), but I can not access to any other sub-directory or file. Nautilus give me an error (Nautilus cannot display « smb://admin@10.0.0.5/alfresco/Projects » ….).
But smbclient also works.
Also I can't see my Alfresco server in the network under Linux whereas I have no problem under Windows!