Most likely devede is looking for mplayer in /usr/bin, but you probably have them in /usr/local/bin ?
To find the mplayer and mencoder binaries, as root, do
find / -name mplayer
find / -name gmplayer
At least once you've found them you know how to locate them. Most likely you found them in /usr/local/bin right? You can then make links in /usr/bin to make the binaries accessible "from" there, even though they are located in /usr/local/bin. Use the ln command:
ln -s /usr/local/bin/mplayer mplayer
ln -s /usr/local/bin/mencoder mencoder
If devede still cannot find the files, you can try putting /usr/bin and /usr/local/bin in your path. In a terminal do
Then try devede again.