Eu tenho a mesma situação do DualSportDad. Aqui está a saída do dpkg conforme solicitado pelo Neni.
michel@hp:$ sudo dpkg -l | grep Brother
ii brdcp7040lpr:i386 2.0.2-1 i386 Brother DCP-7040 LPR driver
ii brother-udev-rule-type1 1.0.0-1 all Brother udev rule type 1
ii brscan-skey 0.2.4-1 amd64 Brother Linux scanner S-KEY tool
ii brscan3 0.2.13-1 amd64 Brother Scanner Driver
ii cupswrapperdcp7040:i386 2.0.2-1 i386 Brother DCP7040 CUPS wrapper driver
ii printer-driver-brlaser 3-3build1 amd64 printer driver for (some) Brother laser printers
ii printer-driver-ptouch 1.4-1 amd64 printer driver Brother P-touch label printers
O Ubuntu 16.04 foi uma instalação limpa e eu especifiquei uma conexão USB ao instalar os drivers. A impressora nem sequer tem uma conexão ethernet.
Eu adicionei a regra do udev manualmente, quando as mudanças ao longo das linhas daquelas mencionadas pelo DualSportDad não funcionaram, embora tenham feito o truque em 14.04.