Pessoalmente, suspeito que a maioria dos seus problemas está relacionada ao seu roteador sem fio.
Configure o seu roteador sem fio como descrito aqui então ele atuará como uma ponte em vez de um roteador. Sua rede será muito mais simples e provavelmente funcionará corretamente. Você não precisará de WINS ou DNS. A resolução de nomes baseada em transmissão deve funcionar.
Você não menciona como seus clientes conectados ao roteador sem fio obtêm o endereço IP deles. Eles são configurados estaticamente ou você tem configuração de DHCP. Se você tem a configuração do DHCP, está enviando opções 44 com uma lista de servidores WINS e 46 com o tipo de nó? Se seus clientes não estiverem configurados para usar o servidor WINS, eles não o usarão.
Como alternativa, por que não configurar um servidor DNS na sua caixa Linux e enviá-lo aos seus clientes? Configure uma zona para sua rede local e forneça um domínio de pesquisa para os clientes que correspondam ao domínio que você configurou.