Some thoughts about computer names - with no concrete solutions to your problem:
SME does not automatically create DNS mappings for DHCP clients on the LAN (
http://bugs.contribs.org/show_bug.cgi?id=2388).
As a result, any access using computer names is either using a DHCP reservation (a pre-configured hostname), or it is using NetBios Name Service (NBNS, or WINS). NBNS is controlled by the "nmbd" service on SME, but this doesn't appear to do much unless your SME is configured as a domain controller -- and then only for computers that are joined to the domain.
With no entries in tinydns, and no entries in nmbd, you're relying on Netbios broadcasts to get your workstation name out to the rest of the network. This could be affected by various firewall settings, name caches, or workgroup settings (I don't know if this is how it is supposed to work, but on a network with no WINS/nmbd or DHCP/DNS servers, I seem to always have trouble browsing to computers that aren't configured with the same workgroup as my workstation).