Try plugging in a power source (eg. a 9V battery) to the Arduino while programming it. If that doesn't work I suggest slowing down the programming rate. Not sure exactly how to do that when programming from the IDE.
However try locating the avrdude configuration file: avrdude.conf
Inside that locate the progammer you are using, and add a baudrate line, eg.
programmer
id = "usbtiny";
desc = "USBtiny simple USB programmer, http://www.ladyada.net/make/usbtinyisp/";
type = usbtiny;
baudrate = 9600; # default is 115200 <--- add a slower baud rate here
Or, try uploading the bootloader file from the command line, eg.
avrdude -c usbtiny -p m328p -U flash:w:optiboot_atmega328.hex -B9600
Where "optiboot_atmega328.hex" is the file name (pathname) of the bootloader you want to use, and -B9600 is the (slower than usual) baud rate you are trying to use.