I haven't had any strange problems (yet!) with Params::Validate. I trust you reported them to rt.cpan.org, as I know that Params::Validate is being actively maintained, and the latest release is dated April 04.
I don't remember the specific problem in question, but now that Params::Validate uses XS internally, I'm not surprised if it occasionally produces weird errors. That said, I use it in production code all the time, and it's very widely used as a result of being required by Mason, and I don't get a lot of bug reports.