Encontrei dois problemas distintos, mas estou colocando-os na mesma pergunta, caso estejam relacionados.
Primeiro, minha Lixeira não esvaziava. Parece que estou travando em alguns arquivos, porque vou redefinir meu Macbook e alguns arquivos serão excluídos e, se eu remover um ou dois arquivos aleatoriamente, mais poderão ser excluídos. Alguns desses arquivos tinham caracteres estranhos em seus nomes. Tentei mudar os nomes para caracteres únicos, mas isso não ajudou.
Em seguida, tentei fazer backup do meu Macbook usando o Time Machine. Conectei o HDD que estou usando para isso, mas toda vez que tento iniciar o backup, o Time Machine trava em "Preparando para fazer backup".
Definitivamente, preciso saber como consertar o problema do Time Machine, mas estou curioso para saber como resolver o problema da lixeira também e se esses problemas estão relacionados ou não.
EDIT: Console.app registrou o seguinte esta manhã antes de eu sair em uma viagem. Eu não trouxe o HDD comigo.
6/5/12 7:41:28.312 AM com.apple.backupd: Starting standard backup
6/5/12 7:41:46.877 AM com.apple.backupd: Error -35 while resolving alias to backup target
6/5/12 7:41:58.368 AM com.apple.backupd: Backup failed with error: 19
6/5/12 7:59:08.999 AM com.apple.backupd: Starting standard backup
6/5/12 7:59:10.187 AM com.apple.backupd: Backing up to: /Volumes/Seagate 3TB Mac/Backups.backupdb
6/5/12 7:59:13.308 AM com.apple.backupd: Event store UUIDs don't match for volume: Macintosh HD
6/5/12 7:59:13.331 AM com.apple.backupd: Event store UUIDs don't match for volume: Blank
6/5/12 7:59:13.683 AM com.apple.backupd: Deep event scan at path:/ reason:must scan subdirs|new event db|
6/5/12 8:23:31.807 AM com.apple.backupd: Backup canceled.
6/5/12 8:23:33.373 AM com.apple.backupd: Stopping backup to allow backup destination disk to be unmounted or ejected.
6/5/12 9:51:21.572 PM com.apple.backupd: Starting standard backup
6/5/12 9:51:22.515 PM com.apple.backupd: Error -35 while resolving alias to backup target
6/5/12 9:51:32.741 PM com.apple.backupd: Backup failed with error: 19