Isto não é específico para Cups ou Brother. Mas é um problema de documentação do Ubuntu 13 para impressoras Brother.
Como os drivers da Brother são de 32 bits, quando você tenta executá-los, você receberá um erro de arquivo não encontrado, embora você ainda possa ls-los, arquive-os, (registre-os).
Os documentos da Brother dizem para instalar o ia-32libs. Mas este pacote não existe mais para o Ubuntu 13. A maneira de obter a mesma funcionalidade é via:
sudo apt-get instala gcc-4.7-multilib
Uma vez que este pacote esteja instalado, posso agora executar binários de 32 bits e, assim, a impressora está funcionando agora!