OK with some very general searching with apt-cache, I guessed perhaps "tie-ixhash-perl' was the package I was missing.
Code:
sudo apt-get install libtie-ixhash-perl
which says it's also going to install perl. and perl-modules. Yeah, I can see how that could help.
Anyway, haven't tested it yet but the install finished.