Este tema me tiene ya un poco harto y es que algo en apariencia tan sencillo no consigo hacerlo de ninguna de las maneras.
Como parece que la Arduino UNO no funciona como ISP (yo no he podido usarla y he leido por ahí que no funciona) estoy probando ahora con una Duemilanove.
La MEGA tiene una configuración de pines diferente, así que las conexiones son:
si el atmega2560 tiene el fuse desactivado de programacion por SPI, no vas a poder meterle nada por SPI, tendrás que usar un programador paralelo, por ejemplo el STK500.
O puedes probar con esto: Arduino AVR High-Voltage Serial Programmer