starstuff:
"This board comes from an uncertified manufacturer"
This is the message I get when programming the mega2560 v3.
Since it happens on upload I would turn on verbose upload logging (in Preferences) to see if any of the verbose messages indicate what it is about the board that makes it look "uncertified".
Perhaps uploading the 1.6.1 firmware for the ATmega16U2 and the 1.6.1 Arduino Mega 2560 bootloader would make the board look 'certified'.