Eu procurei no AskUbuntu e cheguei a duas questões sobre o mesmo problema, que eu não pude responder porque não tenho karma suficiente :(. Então, estou postando a solução aqui.
Após a instalação limpa e a instalação do hplip da impressora, instale também o HPLIP Toolbox no centro de software.
Agora, se você usar 'Simple Scan' no painel para digitalizar um documento, o HPToolbox solicitará que você instale o plug-in necessário. Você também pode instalar o plugin diretamente do HPToolbox na guia de ações.
Depois disso, meu scanner funciona perfeitamente.
(Digitalize pela rede para o PC).