/usr/bin/ld: cannot find -lperl

I was trying to install pp, the Perl PAR Packager:

$ sudo cpan pp

I got this error:

/usr/bin/ld: cannot find -lperl
collect2: ld returned 1 exit status
make[1]: *** [par] Error 1
make[1]: Leaving directory `/home/prystasj/.cpan/build/PAR-Packer-0.982-zX8GIO/myldr'
make: *** [subdirs] Error 2
  SMUELLER/PAR-Packer-0.982.tar.gz
  /usr/bin/make -- NOT OK
Running make test
  Can't test without successful make
Running make install
  Make had returned bad status, install seems impossible

I saw a suggestion to install libperl-dev, but I had that package already up-to-date.
By changing this symlink in /usr/lib from:

lrwxrwxrwx 1 root root 15 2009-01-23 15:28 /usr/lib/libperl.so -> libperl.so.5.10

To:

lrwxrwxrwx 1 root root 15 2009-01-23 15:28 /usr/lib/libperl.so -> libperl.so.5.10.0

I was able to install pp:

$ which pp
/usr/local/bin/pp