Did you check if CGI::Fast returns text strings (i.e. with UTF-8 flag set)?

Please note that the absense of the UTF8 flag does not mean that the string is not a text string.

Checking if the UTF8 flag is set, should be done only by people who know about Perl's Unicode internals. To all other people, it will only add to the confusion.

Properly decode and encode, and all will be fine. (Though you may need an occasional utf8::upgrade, see also Unicode::Semantics.)