I think you have quite an old version of the bootloader code. I think some of the original batch reported themselves as atmeger16 or something strange.
You could try avrdude using avr910 or avr109 as an option other than butterfly in the command line.
I don't supose you have a JTAG or ISP programmer handy to update the bootloader 
Might be worth a search over on avrfreaks to see if anyone else has had this issue.
Sadly if you can't program the butterfly with avrdude then there is nothing that the ardunio IDE can do to help as it simply calls avrdude to do the actual programing. 
[edit]You can of course still use the IDE and libraries.. you will just have to program using avrporg/avrstudio[/edit]