Acontece que a configuração vital é o serviço Bonjour na impressora, o que ajuda na descoberta da rede. Ele pode ser ligado indo para a interface da Web do roteador - basta digitar o endereço IP do roteador.
Existe um separador de rede e tem o item "Bonjour" à esquerda. Quando você clica nele, o painel à direita terá uma configuração para ativar o Bonjour no qual você precisa clicar e também pode definir o nome da impressora. Ele aparecerá no seu telefone com este nome. Depois de aplicar as alterações nas configurações, você precisará tentar verificar as impressoras novamente e elas serão exibidas.