Я выяснил, в чем была проблема.
В файле /etc/apache2/mods-enabled/alias.conf была строка Alias /icons/ "/usr/share/apache2/icons/". Закомментил ее и все заработало.
Раньше директория storage не являлась корневой и ссылки на нее имели вид site.com/storage/icons/1.png. Из-за этого, судя по всему, алиас и не срабатывал.
Теперь ломаю голову: откуда этот алиас там взялся и для чего он был нужен.
