Depois de receber esta segunda mensagem, você citou que o sistema de arquivos já está limpo e deve ser capaz de reinicializar (supondo que o sistema não seja reinicializado.) É por isso que a palavra clean aparece nessa mensagem.
Isso não significa necessariamente que o espaço está sendo liberado - embora um pouco possa ser liberado se você estiver escrevendo em um arquivo e seu sistema travou antes que o programa feche o arquivo. Se você está com pouco espaço, há outras alternativas para arrumar as coisas, como aquelas em esta pergunta.
Para um sistema ext2 ou ext3, o fsck normalmente leva alguns minutos ou menos, mas isso depende do tamanho da partição que está sendo verificada. Uma vantagem do ext4 é que o fsck pode rodar ainda mais rápido.