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.