A solução está um pouco distante do gerenciamento de pacotes. A Adobe envia uma nova versão compilada com o flag sse2, então ela está extinta em computadores mais antigos (como o meu Sempron 2400+) O problema é resolvido substituindo libflashplayer.so manualmente.
mkdir /tmp/install_flash
cd /tmp/install_flash/
wget http://engels.manf.nl/archive/flash/flashplayer11_1r102_63_linux.i386.tar.gz
tar -xvzf flashplayer11_1r102_63_linux.i386.tar.gz
sudo cp libflashplayer.so /usr/lib/adobe-flashplugin/
aproveite.
Além disso, você pode fazer o download do plug-in do site oficial da seção "arquivamento".