I've made another step forward :-)
But still not happy :-(
I happen to have an Arduino Uno clone, used this one instead of the Mega2560 as an ISP, same setup as before, now I did burn a bootloader succesfully!!!! :-)
That's the successfull part.
Went on uploading a sketch, the blink example ... no way!
Problem uploading to board. ...
avrdude: stk500_getsync(): not in sync: resp=0x1c
avrdude: stk500_disable(): protocol error, expect=0x14, resp=0x51
That's the sad part :-(
In order to get the bootloader burnt into the atmega328 on the breadboard I had to follow some other guidelines.
The guide at http://arduino.cc/en/Tutorial/ArduinoISP tells me to "Use the Burn Bootloader > Arduino as AVRISP command."
That didn't work at all, with either board (not the original Mega2560 and so the Uno clone).
Instead I followed this guide: http://arduino.cc/en/Tutorial/ArduinoToBreadboard
I had a minimal configuration (8Mhz Internal Clock), no oscillator at hand :-(
Actually I did not do something ... I did not pull the Atmega328 off of the Uno board ... those DIP sockets are damn evil, I fear I will not get it back inside without breaking a few pins ... I guess that's why I couldn't upload any sketch. I wonder if that's mandatory, or there's some way to upload a sketch to the 328 on the breadboard without pulling off the 328 from the Uno board.