I finally got it to print on my Ubuntu system. The problem seemed to be that the drivers from Brother is not 64bit compatible, and I was using a 64bit version of Ubuntu.
I tried on Debian first, after learning from @sampi that he got it to work on Debian. When installing the drivers I got an error message, which I didn't get on Ubuntu, suggesting a 32/64bit issue. So after installing the ia32-libs packages it worked on Debian. I then tried installing a 32bit version of Ubuntu on my server, and now the printer did work.
But I can only get the printer to work through wifi(both on Debian and Ubuntu). No success with the USB cable, but that's not an issue for me.