Heres the exact output. I added the apt-get update to make sure im not missing anything there either...

administrator@virtualserver:/etc/apt$ sudo apt-get update
Hit http://archive.canonical.com hardy Release.gpg
Hit http://security.ubuntu.com hardy-security Release.gpg
Hit http://au.archive.ubuntu.com hardy Release.gpg
Ign http://archive.canonical.com hardy/partner Translation-en_AU
Ign http://security.ubuntu.com hardy-security/main Translation-en_AU
Hit http://archive.canonical.com hardy Release
Ign http://security.ubuntu.com hardy-security/restricted Translation-en_AU
Ign http://security.ubuntu.com hardy-security/universe Translation-en_AU
Hit http://archive.canonical.com hardy/partner Packages
Ign http://security.ubuntu.com hardy-security/multiverse Translation-en_AU
Hit http://archive.canonical.com hardy/partner Sources
Hit http://security.ubuntu.com hardy-security Release
Hit http://security.ubuntu.com hardy-security/main Packages
Hit http://security.ubuntu.com hardy-security/restricted Packages
Hit http://security.ubuntu.com hardy-security/main Sources
Hit http://security.ubuntu.com hardy-security/restricted Sources
Hit http://security.ubuntu.com hardy-security/universe Packages
Hit http://security.ubuntu.com hardy-security/universe Sources
Hit http://security.ubuntu.com hardy-security/multiverse Packages
Ign http://au.archive.ubuntu.com hardy/main Translation-en_AU
Hit http://security.ubuntu.com hardy-security/multiverse Sources
Ign http://au.archive.ubuntu.com hardy/restricted Translation-en_AU
Ign http://au.archive.ubuntu.com hardy/universe Translation-en_AU
Ign http://au.archive.ubuntu.com hardy/multiverse Translation-en_AU
Hit http://au.archive.ubuntu.com hardy-updates Release.gpg
Ign http://au.archive.ubuntu.com hardy-updates/main Translation-en_AU
Ign http://au.archive.ubuntu.com hardy-updates/restricted Translation-en_AU
Ign http://au.archive.ubuntu.com hardy-updates/universe Translation-en_AU
Ign http://au.archive.ubuntu.com hardy-updates/multiverse Translation-en_AU
Hit http://au.archive.ubuntu.com hardy-backports Release.gpg
Ign http://au.archive.ubuntu.com hardy-backports/main Translation-en_AU
Ign http://au.archive.ubuntu.com hardy-backports/restricted Translation-en_AU
Ign http://au.archive.ubuntu.com hardy-backports/universe Translation-en_AU
Ign http://au.archive.ubuntu.com hardy-backports/multiverse Translation-en_AU
Hit http://au.archive.ubuntu.com hardy Release
Hit http://au.archive.ubuntu.com hardy-updates Release
Hit http://au.archive.ubuntu.com hardy-backports Release
Hit http://au.archive.ubuntu.com hardy/main Packages
Hit http://au.archive.ubuntu.com hardy/restricted Packages
Hit http://au.archive.ubuntu.com hardy/main Sources
Hit http://au.archive.ubuntu.com hardy/restricted Sources
Hit http://au.archive.ubuntu.com hardy/universe Packages
Hit http://au.archive.ubuntu.com hardy/universe Sources
Hit http://au.archive.ubuntu.com hardy/multiverse Packages
Hit http://au.archive.ubuntu.com hardy/multiverse Sources
Hit http://au.archive.ubuntu.com hardy-updates/main Packages
Hit http://au.archive.ubuntu.com hardy-updates/restricted Packages
Hit http://au.archive.ubuntu.com hardy-updates/main Sources
Hit http://au.archive.ubuntu.com hardy-updates/restricted Sources
Hit http://au.archive.ubuntu.com hardy-updates/universe Packages
Hit http://au.archive.ubuntu.com hardy-updates/universe Sources
Hit http://au.archive.ubuntu.com hardy-updates/multiverse Packages
Hit http://au.archive.ubuntu.com hardy-updates/multiverse Sources
Hit http://au.archive.ubuntu.com hardy-backports/main Packages
Hit http://au.archive.ubuntu.com hardy-backports/restricted Packages
Hit http://au.archive.ubuntu.com hardy-backports/universe Packages
Hit http://au.archive.ubuntu.com hardy-backports/multiverse Packages
Hit http://au.archive.ubuntu.com hardy-backports/main Sources
Hit http://au.archive.ubuntu.com hardy-backports/restricted Sources
Hit http://au.archive.ubuntu.com hardy-backports/universe Sources
Hit http://au.archive.ubuntu.com hardy-backports/multiverse Sources
Reading package lists... Done
administrator@virtualserver:/etc/apt$ sudo apt-get install linux-headers-`uname -r`
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Couldn't find package linux-headers-2.6.24-12-server