Why is the package gone in 16.04

see https://launchpad.net/ubuntu/+source/avidemux

There is the plan to provide that package, but there was a problem in building it.
Xenial is not yet ready, and the problem will hopefully be fixed until release date.

If you need this package now, you could try a version from a PPA.

Xenial is released, package well be done?

If you look at https://launchpad.net/ubuntu/+source/avidemux and https://launchpad.net/ubuntu/+source/avidemux/+publishinghistory you can see that there were several failed attempts to build a package for xenial.

Bug #1521755 is a request to package avidemux (2.6) for xenial, you could click "affects me" on that one.

You could try manually installing the version for wily on xenial, maybe that works.
Or search for a suitable (and working) version on one of the PPAs https://launchpad.net/ubuntu/+ppas?name_filter=avidemux

.... TWO YEARS LATER ... ubuntu 18.04 LTS released and avidemux cannot be installed from Software Center at all. You can find AppImage ("universal binary") on avidemux homepage, but it does not work with ubuntu 18.04 :-) AviDemux installation is obviously without simple solution :-)