Isso aconteceu comigo recentemente; Fiquei bastante irritado porque esperava que, se não houvesse espaço suficiente, o Time Machine deveria excluir o backup mais antigo.
O problema era que o disco continha apenas um backup (grande) e não tinha espaço para armazenar o delta atual (delta = alterações nos arquivos desde o último backup).
Eu percebi isso quando examinei o conteúdo do disco e vi que havia apenas uma pasta de backup em Backups.backupdb.
Eu usei o Inventário de disco X para examinar o conteúdo do meu disco rígido e identifiquei algumas pastas grandes que não precisavam para ser feito backup. Excluí estes do backup usando "Time Machine" > "Opções" > "Excluir esses itens dos backups". As informações do Disk Inventory X também me levaram a excluir muitos arquivos grandes não utilizados.
Após as duas alterações listadas acima, o backup prosseguiu com sucesso. Eu não tive que iniciar o backup, ele tentou novamente automaticamente. Eu presumo que minhas alterações trouxeram o delta para um tamanho pequeno o suficiente para caber no espaço livre restante no disco de backup.
UPDATE : Isso aconteceu comigo de novo recentemente, e apenas excluir pastas do backup não foi suficiente, então encontrei outro truque. Vamos dizer que você analisa o conteúdo do seu disco rígido e percebe que há uma pasta de 20GB (vamos chamá-lo de UselessStuff) que estava sendo copiada. Você o exclui do backup, conforme descrito acima, mas isso não exclui os backups anteriores do UselessStuff do disco e você ainda não tem espaço suficiente para o backup ser concluído. Como você não precisa de nenhum backup do UselessStuff, você pode entrar no Time Machine, clicar com o botão direito do mouse em UselessStuff e clicar em "Excluir todos os backups ...". No meu caso, isso liberou espaço suficiente para permitir que o backup continue com sucesso.