I have also recently had issues installing a Brother printer on LMDE but I now have it working. I had to replace a Samsung laser printer which was working fine but then developed a fault so I bought a low cost Brother printer to replace it.
To install the drivers I followed the excellent instructions in this thread:viewtopic.php?f=42&t=103900
My system is 64-bit but when I tried installing ia32-libs (the first instruction in the above thread) I got a dependency error. This led me to search the forum and I found this thread:viewtopic.php?f=190&t=122296
which indicated that ia32-libs was no longer required as it had been superseded by Multiarch. Following the instructions on that post I discovered that my system was running Multiarch so I didn't install ia32-libs.
I followed all the other instructions for installing the printer driver but I couldn't get the printer to work. It was being recognised by my system but whenever I tried printing nothing would print off.
This led me to more searches and it appears that quite a few people have this issue. One suggestion was to add myself to the lpadmin group using the command
sudo usermod -a -G lpadmin YourUserName
but that didn't work for me.
I also came across this blog http://likeaflowingstream.blogspot.co.u ... nters.html
where the blogger has resolved the issue by updating their system using the Debian stable and testing branches but I didn't want to go down that route in case I broke my system.
Another relatively new post I came across in a LM thread mentioned installing ia32-libs to get their printing working so I decided to install it. For some reason there was no dependency issue this time, and once installed I was able to print off pages.
A long tale but basically if you follow all the instructions in the first thread above it should work for you.