No Utilitário de Disco, você vê uma partição mestre e, quando criptografa o disco, uma partição filha é usada. A exclusão de recriação dessa partição filho não funcionou e o problema continuou aparecendo. Apagar a partição principal resolveu o problema. Portanto, parece que a partição principal tinha um problema, o que fazia com que o Time Machine não funcionasse corretamente.
Após apagar a partição principal, criar uma partição filho criptografada, o Time Machine funcionou e eu consegui criar um novo backup.