New Microcontroller - programmer is not responding -
I managed to fix the problem by downloading the latest version of the Arduino IDE from their website and works fine now.

I use Linux mint 18 and installed Arduino via apt and I really do not know why I managed to install the boot loader, but failed with uploading the Sketches.