Como mencionado por Craig Ringer, eu fiz um novo backup e verifiquei e depois de configurar o servidor slave funcionou.
Mas enquanto eu estava fazendo tudo isso eu também lembrava que havia um servidor antigo que também era um escravo do antigo mestre db (A) (aquele servidor não deveria estar rodando e é por isso que eu não pensei inicialmente disso). De qualquer forma, depois de derrubar o velho escravo, fazer backup e restaurar novamente, simplesmente funcionou.
Como eu disse, inicialmente pensei que era por causa de um backup ruim, mas acabou sendo uma mensagem de erro sendo produzida por um terceiro servidor (segundo db escravo). Só para provar meu ponto, iniciei o servidor antigo e recebi novamente as mensagens de erro.
2015-10-31 10:26:37 CET ERROR: requested starting point 19/FE000000 on timeline 1 is not in this server's history
2015-10-31 10:26:37 CET DETAIL: This server's history forked from timeline 1 at 19/FDCF9BA0.
Então, parece que a replicação estava funcionando sozinha, mas essas mensagens de erro feitas por uma segunda replicação estavam me jogando fora.
Novamente, obrigado Craig pela ajuda.