I faced a similar situation here, although we're primarily concerned with French names. I currently use

sub clean {
    my $s = unidecode(shift);
    $s =~ s/[^A-Za-z0-9'-]+/ /g;
    return $s;
}
[download]

Text::Unidecode's unidecode will strip accents, while the substitution will get rid of leftover weird characters. unidecode will do a lot more than just that, though, so it might be a viable solution for you.

The main problem either approach present is when you have to deal with oriental names ( Korean, Japanese, Chinese, etc )

Perhaps you should ask for the name as it appears on the passport. They are romanised.