Hi,
You should install avrdude separately and not use the one bundled with the Arduino software - I have seen other people having problems with the bundled one as well.
I recommend downloading either WinAVR: http://winavr.sourceforge.net/ if you are running Windows or CrossPack: http://www.obdev.at/products/crosspack/index.html if you use MAC OS X. As they include all you will ever need like: a compiler (avr-gcc), programmer (avrdude), and debugger (avr-gdb) plus more.
You can also just download avrdude seperatly: AVR Downloader/UploaDEr - Summary [Savannah], but I can't see the point, as WinAVR and CrossPack is just way faster to get installed.
Hope that did the trick 
Regards
Lauszus