guarda in /usr/local/lib, dovrebbe essere lì, se c'è:
ln -s /usr/local/lib/"tutto quello che trovi di lame" /usr/lib
e installa di nuovo mplayer