I got a MFCJ-625DW wifi printer, it worked with Ubuntu but not LMDE, the installation went well but it just won't connect, any idea ?

Has Brother got a linux driver for the printer? If you check, and its model # is not listed, the find out from support which printers yours replaced. Ex., in HP drivers, even some of the oldest drivers for HP printers will still work on the latest printers, i.e., the HP LJ4 drivers would work for any 4xxx model number HP. I've never checked on this w/Brother, but I bet they do the same thing.

Yes, it worked on Ubuntu, there are 2 types of driver, one is the deb package the other is a network installer both worked on Ubuntu, but on Mint something is missing, the installation went well but it just won't connect.

Sorry, I can't think of anything to tell you. Since LM is Ubuntu based which is Debian based, it should work. You might have to do a little more research/experimenting, then repost the question with the results you have found. There's an Ubuntu tweaks app (if I remember the name correctly) that you could install. It has some other settings that are available, but since I don't have a working linux system right now, I can't say if there are any printer or wifi settings to be adjusted. Have you opened Synaptic, and typed in 'brother' in the search box? Or 'printer' or 'wifi/wireless'? Sometimes when I needed to do something, that's what I'd do. Then just read all the descriptions, and install what I thought would do the trick. That's a way to find software that will solve your problems.

LMDE is Debian based not really Ubuntu, and I've no problem with Ubuntu.

Yes, you are right, I totally forgot.