O problema é o seguinte (de man rsync ):
... The files must be identical in all preserved attributes (e.g. permissions, possibly ownership) in order for the files to be linked together.
No seu caso, as permissões dos arquivos são (de seus exemplos)
Access: (0644/-rw-r--r--) # hardlink failed (original)
Access: (0777/-rwxrwxrwx) # hardlink failed (backup)
Access: (0777/-rwxrwxrwx) # hardlink created (original)
Access: (0777/-rwxrwxrwx) # hardlink created (backup)
Por exemplo
$ chmod 777 A/file
$ rsync -az A/ B/
$ chmod 644 A/file
$ rsync -az --link-dest=$PWD/B/ A/ C/
resulta em
$ du -hsc A B C
965M A
965M B
965M C
2.9G total
enquanto, redefinir as permissões para o original, resulta em
$ chmod 777 A/file
$ rsync -az --link-dest=$PWD/B/ A/ D/
$ du -hsc A B D
965M A
965M B
4.0K D
1.9G total
Você pode tentar com algum arquivo para fazê-lo funcionar (acho que com --size-only , que deve pular arquivos de tamanho igual).
O que você deve fazer é tentar descobrir se você alterou as permissões após o último backup ou, em caso negativo, por que as permissões foram alteradas no diretório de backup.