Emacs23 23.3+1-1ubuntu4 and UTF-8 files - doesn't seem to work

I've been trying to edit UTF-8 files with emacs (emacs23 23.3+1-1ubuntu4) but it doesn't seem to work.
The UTF-8 characters don't appear (I get boxes) and emacs doesn't want to save the file in utf-8, asking me instead to choose a different format.
I can view the files with less without any problems (before I attempt to edit them with emacs - once emacs tries to save them back they seem to be damaged).
I've also tested it with the UTF-8 sampler page found here (same results): http://www.columbia.edu/~fdc/utf8/

Xemacs seems to be having the same problems too (xemacs21-mule 21.4.22-3.1ubuntu1).

ProblemType: Bug
DistroRelease: Ubuntu 11.10
Package: software-center 5.0.3.1
ProcVersionSignature: Ubuntu 3.0.0-15.25-generic 3.0.13
Uname: Linux 3.0.0-15-generic x86_64
NonfreeKernelModules: fglrx
ApportVersion: 1.23-0ubuntu4
Architecture: amd64
Date: Wed Jan 11 20:41:51 2012
InstallationMedia: Ubuntu 10.10 "Maverick Meerkat" - Release amd64 (20101007)
PackageArchitecture: all
ProcEnviron:
 PATH=(custom, no user)
 LANG=en_GB.UTF-8
 SHELL=/bin/bash
SourcePackage: software-center
UpgradeStatus: Upgraded to oneiric on 2011-10-17 (86 days ago)