"I thought CPAN is supposed to install the the dependencies it needs"

It should do, but it depends on the configuration you have. Set:

cpan> o conf prerequisites_policy follow
cpan> o conf build_requires_install_policy yes
cpan> o conf commit
[download]

Better still, just use cpanm.

Update: o conf will list the various key/values your config has.