Have you tried File::Find::Rule? It's basically a well designed OO interface that encapsulates (and extends) the File::Find functionality. I don't know exactly what you're doing, but I should think you would be able to do it more cleanly (from aesthetic and "programmer's sensibilities" standpoints) than with File::Find.
I agree that File::Find's interface is messy. It's a really useful module, but every time I use it I feel like I need to go take a shower afterwards. File::Find::Rule is much less dirty.