Resolution (on new install of Fedora 9 anyway)
PLEASE: Someone who understands how I fixed this should rewrite the important parts so no-one else has to read my novel.
I've had the same problem, new install and things are missing some perl "4:5.10.0-20.fc9" file and it said some gibberish about dependencies. I had originally intended to post my error message and give a progress report, but... it just fixed itself. Here's how:
I used the automatic system updater and it told me I had several perl related dependency issues. I went through the (long) list a handful at a time applying updates until I found the 9 that wouldn't work. A few perl, a few seemingly unrelated, but I'm assuming they used perl scripts?
Then I tried each of them a few more times thinking maybe I had updated something else they needed.
Then I tried to add the "perl programming language" through "add/remove software" thinking it might find dependency issues and resolve them. It did say there were issues and tried to add other packages, but it failed missing the same "4:5.10.0-20.fc9" thing.
Then I closed all the update and add software stuff out, came here looking for help, reopened the add software and and hit update so I could copy the error message, but it updated fine.
The end. Someone who better understands what I did please rewrite the important stuff out of here so people don't need to read my novel.