Hello Till, I'm sorry if my English is not as good as I would.
I had the same problem with an Brother HL-4150CDN with 12.04 version but I've solved (provisional) by changing the driver (HL-4150CDN for CUPS) for another (HL-4050-CDN) that had a problem in previous versions (with the same printer) but now it works perfectly.
Hello Till, I'm sorry if my English is not as good as I would.
I had the same problem with an Brother HL-4150CDN with 12.04 version but I've solved (provisional) by changing the driver (HL-4150CDN for CUPS) for another (HL-4050-CDN) that had a problem in previous versions (with the same printer) but now it works perfectly.
I found the HL4150CDN driver at http:// welcome. solutions. brother. com/bsc/ public_ s/id/linux/ en/download_ prn.html and it worked fine from 10.?? to 11.10 versions but no with 12.04.
Perhaps this information wuld be useful for you.