As you've already mentioned, support for character and byte strings is the most important new feature. In connection with localization, there's the Encode module which allows for character set conversions; dollar sign reordering in printf; Locale::Maketext for localized messages; and I18N::Langinfo to query locale data.

Another feature is restricted hashes which will replace pseudohashes as the underlying mechanism of fields from perl 5.9: see Hash::Util.

Then there's safe signals, of which you've probably heard of.

Source filtering, see Filter::Util::Call.

Other smaller new features are brackets in prototypes (see perlsub), the new ${^TAINT} variable, newly overridable and tieable builtins, the CLONE function, improved attributes and lvalue functions, loads of new core modules (such as List::Util or Tie::File etc), better bignums, better perlio layers.

You may want to read the short Highlights In 5.8.0 section of perl58delta.

Update 2006 oct 6: corrected spelling -- thanks to ysth.