Maybe this is too obvious to even suggest, but have you tried messing around with the import options in Excel?
Not sure what version of Excel you have, but something like this?
I only suggest it since it seems like there should be a way to get Excel to recognize a UTF-8 text file, at least I'd hope that's a problem Microsoft has licked at this point. But I'm told I often give Microsoft too much credit. :-)
UPDATE: Or instead of importing the text file you create in to Excel you could try having Perl create the Excel file directly?