Что у вас говорит
nm -D /usr/sbin/nagios |grep PL_perlio_mutex

# nm -D /usr/sbin/nagios |grep PL_perlio_mutex
0000000000670990 B PL_perlio_mutex

К сожалению, здесь также издержки сборки snapshot'ов.
Дело в том, что nginx требует libperl.so.5.8(PERL_5.8.9).
Но этот интерфейс комплектовался "постепенно", то есть в него время от времени
что-то добавлялось.  Я четко следил за тем, чтобы ни один перловый модуль не
использовал новых функций из PERL_5.8.9.  Но штуки типа nginx лезут слишком
глубоко, потому что встраивают в себя собственный перловый интерпретатор.

Так вот, perl-base-5.8.8-alt4 уже предоставляет интерфейс PERL_5.8.9, и
зависимость на libperl.so.5.8(PERL_5.8.9) оказывается разрешенной.  Тем не
менее, в этой версии perl-base интерфейс libperl.so.5.8 ещё не предоставляет
всех функций, которые добавились в него позднее.

А с перемнной "B PL_perlio_mutex" существует отдельный класс проблем, я написал
об этом в devel. 
http://lists.altlinux.ru/pipermail/devel/2007-September/062742.html

Ok, прочитал.  Не то чтобы мне этот дефект был принципиален, просто
"неаккуратненько"..

Признаю проблему не решаемой.  Фактически все пакеты, которые требуют
libperl.so.5.8(PERL_5.8.9), могут также неявно требовать версию perl-base не
меньше той, с которой были собраны.  Таких пакетов заведомо немного:

$ apt-cache showpkg 'libperl.so.5.8(PERL_5.8.9)' |grep '^  ' |sort -u
  apache2-mod_perl,libperl.so.5.8(PERL_5.8.9)
  nagios,libperl.so.5.8(PERL_5.8.9)
  nginx,libperl.so.5.8(PERL_5.8.9)
  perl-devel,libperl.so.5.8(PERL_5.8.9)
  perl-suidperl,libperl.so.5.8(PERL_5.8.9)
$

То есть, по сути, таких пакетов всего три: apache2-mod_perl, nagios и nginx.
Ни один перловый модуль не подвержен этой проблеме, для этого я специально
патчил перл.

Зависимость на перл какого вида надо ставить на такие пакеты?

Не знаю.  Лучше никакую не ставить.
В принципе неплохо бы ставить автоматически...