O zsnes existe no repositório Universe apenas para o 32bit Natty.
Se você olhar aqui no launchpad para o pacote zsnes, você notará que não há pacote de 64 bits disponível - apenas o pacote de 32 bits (i386).
Para que isso funcione com 64 bits, é necessário um pouco de trabalho no terminal ...
Faça o download do pacote de 32 bits aqui na pasta Downloads.
Instale todas as dependências:
sudo apt-get install libao4 libc6 libgcc1 libgl1-mesa-glx libpng12-0 libsdl1.2debian libstdc++6 zlib1g
Faça o seguinte:
cd ~/Downloads
dpkg -x zsnes_1.510-2.2ubuntu4_i386.deb zsnes_dir
cd zsnes_dir/usr/bin
Agora você pode executar o aplicativo executando
./zsnes -ad sdl