Такая же проблема.
Выдает :
Чтение списков пакетов… Готово
Построение дерева зависимостей
Чтение информации о состоянии… Готово
E: Не удалось найти пакет php
E: Не удалось найти пакет libapache2-mod-php
E: Не удалось найти пакет php-mcrypt
E: Не удалось найти пакет php-mysql
Только я ставлю Apache2/MySQL/PHP