The F-9 package of perl-Digest-Nilsimsa has modules in "perl 5.8.8" paths, which are not found by F-9's perl 5.10.0. The package therefore needs rebuilding for perl 5.10.0. There was a mass rebuild of perl packages late in the F-9 development period but this package missed out on it, possibly because it is missing a perl version "module compat" dependency and hence didn't have broken deps when perl was upgraded to 5.10.0. Since the ACLs are open for this package, I'll go ahead and fix it myself.
perl-Digest-Nilsimsa-0.06-10.fc9 has been submitted as an update for Fedora 9
perl-Digest-Nilsimsa-0.06-10.fc9 has been pushed to the Fedora 9 testing repository. If problems still persist, please make note of it in this bug report. If you want to test the update, you can install it with su -c 'yum --enablerepo=updates-testing update perl-Digest-Nilsimsa'. You can provide feedback for this update here: http://admin.fedoraproject.org/updates/F9/FEDORA-2008-5936
perl-Digest-Nilsimsa-0.06-10.fc9 has been pushed to the Fedora 9 stable repository. If problems still persist, please make note of it in this bug report.