Did I just brick my ATMEGA 2560?
Ah, the problem seems to be in the IDE - Something with the fuses when programming the mega (I won't even pretend to understand that yet).
I upgraded to 1.6.12 and everything works like a charm.

Best regards
Stefan