For what it's worth, I've been struggling with a very similar problem for ages, and in the end it appears that HTML::Entities was causing my problem.
Since you're using it here, have a look at that. It encodes the characters directly (using char()) I believe, and I don't think it supports UTF8. I could be wrong, but that's what was causing my problem.