For some reason the avrdude binary that is shipped with arduino-0018 has no support for the USBtiny programmer which I use to burn bootloaders on blank AVR atmega328 microcontrollers.
On Debian the workaround is simple: first install avrdude via apt-get/aptidude and then enter the hardware/tools directory in the arduino-0018 dir and replace avrdude by a softlink to /usr/bin/avrdude like this:

$ cd arduino-0018/hardware/tools
$ mv avrdude avrdude.old1
$ ln -s /usr/bin/avrdude .
$ mv avrdude.conf avrdude.conf.old1
$ cp /etc/avrdude.conf .

After this burning a bootloader via the menu in arduino works fine again. A similar approach will probably work on other Linux distributions.