In linea generale quando succede qualcosa di non comprensibile cerco di capire quale possa essere la causa ponendo mi alcune domande del tipo:

- Prima del verificarsi del problema cosa è stato variato?
Nel tuo caso, precedentemente alla scoperta del problema, è stata fatta qualche variazione al DB? E' successo qualcosa alla struttura del DB che possa aver influenzato il backup?

Oppure potrebbe essere stata "colpa" di informazioni inserite nel DB? In quel punto che tipo di dati ci sono?

Ancora... i caratteri strani sono sempre nello stesso punto oppure sono "casuali"?

Successivamente per capire meglio farei delle prove variando le condizioni o utilizzando altri strumenti.
Ad esempio, vedo che fai il dump e lo comprimi. Se non comprimi il backup i dati sono corretti?
Se fai il backup con altri strumenti, ad esempio semplicemente l'export con phpMyAdmin cosa succede?

Vediamo se con maggiori elementi si capisce qualcosa