If you know for sure that Windows and Linux users can access the SMB shares when the firewall is not running then it is a problem with the firewall. I don't run SMB shares but here is how I would approach the problem.
Find a Windows or Linux machine that wants to access the share and get it's ip address, say x.x.x.x. Then create a rule to allow full access for this address
ipfw add ????? allow log ip from x.x.x.x to any in
Remember to place this rule nice and early in the list (the rule number is at ?????). Now turn logging on and try to access the share (which should succeed). Having done that turn off logging and examine the log file for all references to x.x.x.x This will show you the ports and protocols (tcp, udp, icmp) that were used with the connection. You should be able to work from that. Remember the legitimate ports are usually less than five digits.
Then remove rule ?????.