Intente eliminar el último / al final de la ruta del directorio para excluir
tar -pczf MyBackup.tar.gz --exclude="/home/user/public_html/tmp" /home/user/public_html/
Tenga en cuenta que el exclude argumento:
1- Debe usarse con un = , así:--exclude=PATTERN
2- Espera un patrón (como señaló el usuario Don Dilanga), no un directorio, aunque un directorio funcionará bien como patrón si es lo suficientemente largo como para no coincidir con ningún archivo individual.
3- Debe colocarse antes del directorio de origen. (como lo señaló kghbln)
Intenta mover el --exclude antes de incluir.
tar -pczf MyBackup.tar.gz --exclude "/home/user/public_html/tmp/" /home/user/public_html/