You're right in assuming this is a charset issue. You need to set the appropriate environment variables to the beginning of your crontab.
Something like this should work:
LANG=en_US.UTF-8
LC_CTYPE=en_US.UTF-8
Optionally use LC_ALL in place of LC_CTYPE.
Reference: http://opengroup.org/onlinepubs/007908799/xbd/envvar.html
Edit: The reason it displays fine when you run it in your shell is probably because the above env vars are set in your shell.
To verify, execute 'locale' in your shell, then compare to the output of a cronjob that runs the same command.
Re-Edit: Ok, so it's not an env var problem.
I am assuming you're using mailx, as it is the most common nowdays. It's manpage says:
The character set for outgoing
messages is not necessarily the same
as the one used on the terminal. If an
outgoing text message contains
characters not representable in
US-ASCII, the character set being used
must be declared within its header.
Permissible values can be declared
using the sendcharsets variable,
So, try and add the following arguments when calling mail:
-S sendcharsets=utf-8,iso-8859-1