Problema resolvido!
Para qualquer pessoa interessada, aqui está a minha solução:
Foi update-initramsfs que causou os erros acima (predicado inválido -regextype 'find: invalid predicate -regextype').
As imagens initrd criadas foram quebradas.
Algo estava errado com findutils , então eu apenas reinstalei o pacote (assim como initramfs-tools ) e o problema se foi :-)
Obrigado mais uma vez por ajudar.