Arduino Board malfunctioning
You mention that you are running the the AVR 5v and GND line to the breadboard, if your circuit is drawing more than a little bit of current (powering amplifiers and other active elements) you should use a separate regulator, dips in Vcc, especially at power up, when the bootloader is trying to write the flash, can prevent the read/write operation from completing fully with the application section getting corrupt (not properly written sketch) or the avr loading/executing the wrong instruction from the bootloader (preventing application write). If your data lines are being used to source significant current (multiple LED's) you should also reconsider your circuit layout for the same reason. Since the bootloader is working properly when disconnected from the breadboard, and you've already excluded other problems like the tx/rx line being interfered with by outside devices (by connecting something to pin0) and random resets.

In the atmega datasheet (page 278) there is a buried section that states


  During periods of low VCC, the Flash program can be corrupted because the supply voltage is
  too low for the CPU and the Flash to operate properly. These issues are the same as for board
  level systems using the Flash, and the same design solutions should be applied. 
  A Flash program corruption can be caused by two situations when the voltage is too low. 
  
  First, a
  regular write sequence to the Flash requires a minimum voltage to operate correctly. 
  
  Secondly,
  the CPU itself can execute instructions incorrectly, if the supply voltage for executing instructions
  is too low.
  
  Flash corruption can easily be avoided by following these design recommendations (one is
  sufficient):
  
  
  If there is no need for a Boot Loader update in the system, program the Boot Loader Lock 
  bits to prevent any Boot Loader software updates.
  Keep the AVR RESET active (low) during periods of insufficient power supply voltage. 
  This can be done by enabling the internal Brown-out Detector (BOD) if the operating voltage matches the detection level. If not, an external low VCC reset protection circuit can be 
  used. If a reset occurs while a write operation is in progress, the write operation will be 
  completed provided that the power supply voltage is sufficient.
  Keep the AVR core in Power-down sleep mode during periods of low VCC. This will prevent the CPU from attempting to decode and execute instructions, effectively protecting 
  the SPMCSR Register and thus the Flash from unintentional writes.
  


In the worst case this can result in the bootloader flash section getting corrupt.