Добавляем репозиторий и обновляем индекс пакетов:
sudo add-apt-repository ppa:sergey-dryabzhinsky/php55
sudo apt-get update
При этом искать нужные пакеты надо так:
sudo apt-cache search php55
-- т.е. они начинаются на "php55" (а не "php5.5").
Спасибо: https://launchpad.net/~sergey-dryabzhinsky