Given that you've got a grip on most of the problem, I'd take a look at Lingue::EN::NameParse which might give you what you are looking for. I've used it in the past, and I seem to remember that I works fairly well.

--hsm

"Never try to teach a pig to sing...it wastes your time and it annoys the pig."