Hmm. When my arduino AVR lost it's bootloader, I used avrdude in "bare" form with an STK-500 to re-install the bootloader, and then went back to using the (unmodified) Arduino IDE to download sketches using the (fixed) normal bootloader...
(The problem with helping people fix bootloader problems is that it usually takes some sort of ADDITIONAL AVR programmer to fix, which takes it out the "easy" category. A generally "correct" piece of advice is that if your brand new arduino doesn't upload programs, you should contact the vendor for advice or replacement. But that's so "general" as to not be very helpful.)