When my Arduino can no longer be programmed with the serial USB port, I use the ICSP pins to reload the bootloader. So far that method has resolved problems every time for me.
I've found the single most reliable way to program the Arduino is with a USBASP programmer. You can find them on ebay for just a few bucks. I suggest getting one with 3.3/5V selectable voltage, as well as a 10 pin to 6 pin adapter. (the USBASP typically has 10 pins, Arduino has 6).
With the USBASP, you can also easily reload the bootloader (see tools - burn bootloader). This will typically allow you to again program via the on-board USB connection.
This site has great resources: USBasp - USB programmer for Atmel AVR controllers - fischl.de
Note that the drivers need to be installed manually. Zadig is a great resource for this: http://zadig.akeo.ie/
Be sure to only plug in the USBasp device to the computer, NOT the Arduino (you don't want to have multiple sources powering the Arduino, you might fry something). Remove the ICSP cable if you go back to programming with the on-board Arduino USB connection.
I've included more detailed instructions and pictures here:
Hope this helps...