Hmm, you're probably run into issues with userelocatableinc . It was enabled by default for perl version >= 5.15.5 and worked fine on Mac/Linux, but apparently it has issues on other platforms.
For now you may try to re-install perl-5.16.1 again by doing
PERLBREW_CONFIGURE_FLAGS="-de" perlbrew install perl-5.16.1
(After a `perlbrew uninstall perl-5.16.1` -- that essentially rm -rf the directory.)
However I believe if you put full path shebang in your programs it should be good to run. It's just the perlbrew switching function that does not work well.