Out of curiousity are you running LMDE 32 or 64 bit, not that it's much use but I'm running LMDE 32 on an AMD 64 machine bit and zsnes works fine.
Note: I'm not sure if it is 64 bit compatible,
http://www.zsnes.com/index.php?page=news"64 bit users having trouble compiling should know that ZSNES is currently only x86-32 compatible and will not be x86-64 compatible for a while. It is advised in the mean time to setup a 32 bit chroot, or have 32 bit libraries installed and use either a precompiled binary or try to compile yourself in 32 bit mode by passing gcc/g++ -m32." But thats from 2006...
