Вы не опишите, как вы пытались установить?
Есть много способов, я хотел бы придерживаться менеджера пакетов, так что просто:
sudo apt-get install libcatalyst-perl
Обновление:
Ваша проблема, безусловно, заключается в смешанном использовании пакетов CPAN и Debian. Вы должны избавиться от одного, и вы получите его работать.