When using Mint 10 or older, the printer is very slow in processing images as they aren't compressed enough. It may even fail due to lack of memory (64MB should be enough for printing images but it isn't in Mint 10).
With Mint 11, it works fine. It is still a little bit slower than Windows, but not much.
(Windows uses a proprietary protocol for this printer while Linux uses PCL 6)
For users of other distros: you need Foomatic filters 4.0.7 to get the 'Mint 11' performance. I don't know which distros already use that version but I think most 2011 ones do. Not sure about Debian, however. Your distro's package manager may tell you which version of foomatic-filters is installed.
Installing Foomatic 4.0.7 on Mint 10 (using the .deb files from Ubuntu Natty's repository) works also, but does not fully solve the problem.