It seems that the Mapserver binary shipped with Ubuntu 8.04 doesn't support the AGG renderer, and the libagg Ubuntu package doesn't supply the required .so version of the library. But it's quite easy to get AGG support, here's how I did it:

apt-get build-dep libagg-dev
apt-get source libagg-dev

These steps create make sure the AGG build dependencies are installed, and then retrieve the AGG source into a directory within the current directory.:

cd <agg-dir>
. autogen.sh
./configure --prefix=/usr
make
sudo make install

That installs AGG with an .so format for the library.

Download latest mapserver, get build dependencies for it, and build.:

apt-get build-dep mapserver
wget http://download.osgeo.org/mapserver/mapserver-5.2.0.tar.gz
tar -xzf mapserver-5.2.0.tar.gz
cd mapserver-5.2.0
./configure           \
--prefix=/usr         \
--with-pdf            \
--with-freetype       \
--with-agg            \
--with-eppl           \
--with-proj           \
--with-threads        \
--with-sde            \
--with-geos           \
--with-ogr            \
--with-gdal           \
--with-tiff           \
--with-postgis        \
--with-mygis          \
--with-wfs            \
--with-wcs            \
--with-wmsclient      \
--with-wfsclient      \
--with-sos            \
--with-fribidi-config \
--with-gd

make
sudo make install
cd mapscript/python
python setup build --prefix=/usr
sudo python setup install

That did it for me.