Eu me deparei com esse mesmo problema com uma impressora HP mais recente e HPLIP. O que eventualmente funcionou para mim foi uma versão atualizada do CUPS. Na época, eu tive que compilar manualmente, no entanto, pode ser atualizado no último beta (15.04). Eu não recomendaria atualizar imediatamente sem questionar ... primeiro tente uma versão ao vivo à noite para ver se vai funcionar ou não.