If you have the Arduino with the 328 rather than the 168 it wont work on Ubuntu Hardy 8.04 without compiling gcc from source or upgrading your distro, the version of gcc-avr doesn't have support for 328 and because 8.04 is a LTS (Long Term Support) it wont automatically upgrade gcc as it may make it more unstable for someone who is using a particular feature of it.
My advice would be to either upgrade to the latest version (Karmic Koala) or run Karmic or Windows in a virtulisation eg Virtualbox.