That is exactly why I find it so intriguing that it works with some boards and not others and that you are not really dealing with the board to a certain extent when using the cable (it still relies on the crystal and caps). It is acceptable with the R2 since it maybe fried beyond repair but the R3 is in perfect working order and being programmed on the same computer and software as Nick's sketches. I had a lot of problems with fuses, resonators and crystals with Sanguinololus some time ago, maybe there is something like that here too.
I tried turning the cable around, connecting directly according to his tutorial - it works with other boards but not my Megas - both original ones made in Italy bought from reputable sources.
I have also ordered a proper programmer (AVRISP STK500 V2.0 compatible with 2560's) and will try it out with that and see what happens then.