Eu resolvi meu problema. O problema era como eu suspeitava na atualização da questão. Estou usando um processador Atom @ 1.66 GHZ com 1 GB de memória e, com a nova tela inicial, o fsck e a nova tela inicial plymouth estavam competindo por recursos mais do que minha tela inicial anterior. Eu atualizei o código plymouth, simplifiquei-o e removi todos os recursos e códigos desnecessários e meus tempos de fsck retornaram para cerca de 5 minutos.