Did you su to root and run
to get an up-to-date database of your files? After you run updatedb, do
and if it's found, check the path. I'm assuming avidemux is the command used to start the program. If it's not found, I'd reinstall.