[Moved here by moderator]
On Gnome 2 I think this link from Nautilus to File-Roller is provided by nautilus-actions package. On MATE Nautilus is forked to Caja and File-Roller to Engrampa. I think the root problem is Linux Mint 12 doesn't have the newest version of MATE available. Engrampa is not available in the Linux Mint 12 repository and File-Roller instead is still installed on Linux Mint 12. Checking for Linux Mint 13, Engrampa is in the repositories:
http://packages.linuxmint.com/list.php?release=MayaInstalling nautilus-actions on MATE didn't do anything as expected, but worth a try I thought (it wasn't

). I think this is resolved on Linux Mint 13, but perhaps also a "caja-actions" package will be needed. Perhaps the MATE forums can answer, but I didn't find anything there yet:
http://mate-desktop.org/