OK this looks like another problem. First as I suggested and ikegami too: blank the 2 env vars PERL5LIB and LD_LIBRARY_PATH. I think it is not enough to do that in the shell because perlbrew *may* make decisions based on these. So, make sure that in your shell init (e.g. ~/.bashrc and system-wide /etc/bashrc or something) the first is blank. The 2nd I also believe it should be blank but I am not aware of your local settings or other packages changing it. A good rule of thumb is that the 2nd should not have anything perl-related set during shell init. Later of course perlbrew may set these I am not sure but that's ok.

From the output you cited above, it's weird that the include dirs are taken into account but not the library's (EDIT: not sure whether -L/perbrew/perl/... should be present or not during XS.c compilation.). So, still a mixup. Here is what happens in my linux system without perlbrew:

cp lib/List/MoreUtils/XS.pm blib/lib/List/MoreUtils/XS.pm
Running Mkbootstrap for XS ()
chmod 644 "XS.bs"
"/usr/bin/perl" -MExtUtils::Command::MM -e 'cp_nonempty' -- XS.bs blib
+/arch/auto/List/MoreUtils/XS/XS.bs 644
"/usr/bin/perl" "/usr/share/perl5/vendor_perl/ExtUtils/xsubpp"  -typem
+ap '/usr/share/perl5/ExtUtils/typemap'  XS.xs > XS.xsc
mv XS.xsc XS.c
gcc -c  -I. -D_REENTRANT -D_GNU_SOURCE -O2 -g -pipe -Wall -Werror=form
+at-security -Wp,-D_FORTIFY_SOURCE=2 -Wp,-D_GLIBCXX_ASSERTIONS -fexcep
+tions -fstack-protector-strong -grecord-gcc-switches -specs=/usr/lib/
+rpm/redhat/redhat-hardened-cc1 -specs=/usr/lib/rpm/redhat/redhat-anno
+bin-cc1 -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clas
+h-protection -fcf-protection -fwrapv -fno-strict-aliasing -I/usr/loca
+l/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 -g   -DVERSION=\
+"0.428\" -DXS_VERSION=\"0.428\" -fPIC "-I/usr/lib64/perl5/CORE"   XS.
+c
[download]

Notice that there are quite a few perl-version related things like "/usr/bin/perl", "/usr/share/perl5/vendor_perl/ExtUtils/xsubpp", '/usr/share/perl5/ExtUtils/typemap'. Do all these paths agree with your perlbrew'ed Perl?

P.S. I think you should also send a message to syphilis too about this last error.

EDIT: Bottomline: now that you have perlbrew perhaps start fresh from the beginning to see a) how it is compiled using the new settings (for example to confirm if correct binaries and library paths are used), b) where it fails if it does, c) strace output filtering out noise to see the fullpath of the library failing the handshake. It is important to filter noise and irrelevant bits like the ENOENTs but give us the important bits like what binary creates the XS.xsc - also, it is more convenient for me to deal with this issue with as little delay as possible between replies. It is difficult to me to switch back and forth contexts.