Acabei de me deparar com uma situação semelhante, na minha máquina Ubuntu 16.04, onde tentei imprimir algo e não imprimi. E quando abri as configurações da impressora, mostrei uma mensagem de erro "não é possível localizar a impressora" ou algo do tipo.
Em Impressora, > Configurações, parecia que meu "URI de dispositivo" estava definido com algum valor bizarro. Cliquei no botão Alterar, selecionei "Impressora de rede" e depois de alguns segundos a minha impressora apareceu na lista de impressoras de rede, então eu selecionei e cliquei no botão "Aplicar".
Em poucos segundos, o pedido de impressão que eu havia publicado anteriormente foi impresso automaticamente.
BTW, após as etapas acima, meu "URI de dispositivo" correto (funcionando) se parecia com: socket: //192.168.0.211: 9100
Antes, em vez de um IP numérico, ele tinha algum tipo de string estranha lá.
Uma possibilidade do que pode estar acontecendo é que, algumas vezes, quando o Ubuntu verifica a impressora via WiFi, a conexão wifi pode nem sempre passar, caso em que o Ubuntu inadvertidamente muda o "Device URI" da impressora para algo que o torna inutilizável.
Apenas uma teoria baseada no que acabei de observar há 10 minutos.