ЧЯДНТ?
Что Я Делаю Не Так? Не так был сделан выбор дистриба. Пакетный дистриб, к которому относится бубунта работает по принципу "мы знаем лучше, что вам надо, хавайте, ламеры" (любой пакетный дистриб). Вы получаете упрощение жизни - не нужно знать, как приложения собираются и как они зависят друг от друга, но платите за это тем, что есть некий Джон, который решает, что и какой версии у Вас будет стоять.
Как поставить php5.6 на ubuntu 16.04.07?
Вам - только скачать исходники и поставить вручную, предварительно потренировавшись на кошках, потому что make install может гарантированно снести нахрен все, что ему не понравится.
В чем проблема - в репозитарии, в самой ubuntu, в php?
В выборе типа дистриба. Дистрибов всего два типа - пакетные и source-based. Первые легче и проще в освоении, потому что часть работы ты переложил на сборщика дистриба (но тем самым делегировал ему право решать, что будет стоять у тебя). Вторые в освоении сложнее, они требуют, чтобы ты знал все сам, но зато в нем ты можешь поставить любую версию (две, три, десять) любой программы.