This doesn't occur when using the {current_date} tag.
In the example below, the locale is set to french:
{modified_date format="%A %d %B %Y - %T %Z"} >> jeudi 03 février 2011 - 14:37:42 CET
The current_date does however return a correctly formatted date:
{current_date format="%A %d %B %Y - %T %Z"} >> jeudi 03 février 2011 - 14:43:07 CET
I've tried my best to get it in to UTF-8...
My attempts to fix this:
{modified_date format="%A %d %B %Y - %T %Z"|escape:'UTF8'}
{modified_date format="%A %d %B %Y - %T %Z"|escape:'UTF-8'}
{modified_date format="%A %d %B %Y - %T %Z"|escape:'UTF-8':'UTF8'}
and finally...
{capture assign="modified"}{modified_date format="%A %d %B %Y - %T %Z"}{/capture}
{$modified|escape:"UTF-8"}
The output remains the same...

Any suggestions?
ps: yes, default_encoding & admin_encoding are set to utf-8

Greetings,
Manuel