That message show up when I try to install Ubuntu Server 8.04.2
Looking around, the solution :
apt-get update
apt-get remove linux-server
apt-get install linux-386
apt-get install linux-server
or change linux-386 with linux-generic
will solve that problem.