gettext.pm is in /usr/lib/perl5/Locale and is part of liblocale-gettext-perl.
I see you have /usr/lib/perl5 on the list. Reinstall liblocale-gettext-perl, perhaps?