Dê uma olhada no arquivo /usr/local/Brother/Printer/**your model**/inf/br**your model**rc (provavelmente /usr/local/Brother/Printer/dcp135c/inf/brdcp135crc ) e verifique se o valor de PaperType corresponde ao tamanho do papel.
Isso aconteceu comigo quando as configurações eram "Carta" e meu trabalho era "A4".