What version of perl are you using? Unicode support has drastically changed on the 5.6/5.8 boundaries, and getting a "good" answer may depend on which one you're using.

If you can use any version, try 5.8 (5.8.6 is the latest at this point, I believe). Its unicode support is way better than 5.6 (kudos to p5p!).