Acabei de encontrar uma solução para o evince.
Basicamente, o problema era que eu tinha as atualizações propostas xenial ativadas e havia algum conflito.
Eu apenas segui as instruções do link para fazer o downgrade do atualizações propostas e voltar para os estáveis.
Depois disso, o evince está funcionando como antes e eu posso digitar no campo de pesquisa. Após o rebaixamento, tive alguns problemas com a placa de áudio, mas depois de algumas reinicializações a frio, tudo deu certo.