Good knowledge in some other area would have made it a lesser issue that they didn't have OO experience, but they were generally lacking knowledge across the board.
Your proposed salary was low, your offering uninteresting, etc.
Myself, I crossed Perl and Python (and Ruby, and Smalltalk, and Lisp and many others) from list of languages to discriminate good programmer from not so good one a long time ago. They just did not get used in anything I consider interesting or important (but I still prefer domain knowledge - so lisper with relevant past is still interesting).
Right now I would use Haskell (or even stronger typed language like Coq or Agda) as a requirement, and my proposal would include DSeL for problem domain with Perl backend (if Perl is that necessary).
I will get much less resumes initially, those resumes will be of higher quality and my employee will produce a tool that allow me (us as a team, actually) to retarget our product to another backend quickly if we need to do so.
Actually, I specifically searched for a language that wasn't OO but provide all the benefits of OO when I found Haskell. The standard library back then was about twenty or less modules.
I don't really match against most of my colleagues right now, they done much more OO than me.
So, until recently I was really competent programmer with Haskell experience in useful programs that hadn't done OO. ;)
Formlets: http://hackage.haskell.org/package/formlets and then http://groups.inf.ed.ac.uk/links/formlets/
Does he still need to be proficient in OO?
What if your candidate knows much about your current problem domain? Do you still prefer someone who doesn't know a bit but proficient in OO?