It looks like on a previous system you installed libintl with a binary package from Rudix. You could try reinstalling from there, but their website indicates Yosemite is a "work in progress".

What I would do in your position is to try to (re-)install everything you need — mutt, t-prot, gettext/libintl, and even another version of perl with Locale::gettext if necessary — through MacPorts. This works similar to Perlbrew in that the applications get placed in a directory structure (/opt/local/ by default) which is then added to the user PATH. If something goes wrong you can simply delete the entire tree under /opt/local/ and nothing else will be affected.

I personally would delete the old stuff and directories as well, including remnants of Perl v5.16 and v5.12, but leaving the v5.20 under Perlbrew and of course leaving the system v5.18 which is used by Yosemite. As it is, you have partial pieces from old installs, making it hard to troubleshoot.

MacPorts has been around a while, has a good reputation, and I'd suspect you could get good advice and help on their IRC channel. Another similar option to MacPorts for installing open source applications in OSX is Fink, which you may also want to consider as an alternative.

I think you are likely to get better answers from a place like the IRC channel for MacPorts than here because your problems are more with the open source applications and dependencies than they are with Perl itself.