Know this is old but I ran onto it during my search for Nano(V3)'s not uploading so thought might help someone else. Problem is the bootloader - Arduino IDE BUT I Found an easy solution (right under my nose).
I realized that my nano's had been uploading just fine then I had finally updated the Arduino IDEAVR Boards from 1.6.20 to 1.6.21. I didn't think there was any problems because it still showed my Nano and ATmega328 etc in the board manager after the change.
But the new boards manager has a new ATmega328 processor choice for the Nano. I changed processor: In the Arduino IDE select TOOLS > PROCESSOR > pulldown menu from ATmega328P to "ATmega328P (Old Bootloader)".
Since then, I have uploaded many programs to several different Nano's V3 (Prolofic interace Chipset) without issue.