If I substitute use utf8; for use encoding 'utf8'; it works fine (perl 5.8.8/debian linux).

I note that the documentation for encoding says: "allows you to write your script in non-ascii or non-utf8". Still, I would expect your code to work, assuming your script really is utf-8 encoded.