I had a similar problem: a very long delay when I first ran avrdude before it started to do anything. I had to actually patch avrdude to fix it. Arduino 0009 (which should come out tomorrow) will include the patched version and a "Burn Bootloader" command.
I submitted a bug to avrdude: AVR Downloader/UploaDEr - Bugs: bug #19882, Many "error in USB... [Savannah] but haven't heard anything. You might want to add a comment explaining your experience (with the long delay on startup). These things sometimes get fixed faster if multiple people report them.