Tranquilo que sí se puede.
Tuve problemas haciendo lo mismo al mirar en arduino.cc cómo meterle el bootloader a un ATMEGA328P (el del UNO), usando como programador un Mega.
El conexionado que viene en Learning (http://arduino.cc/es/Tutorial/ArduinoISP si lo ves en castellano) es incorrecto para nuestro caso, pues SOLO vale para programar un UNO desde otro UNO.
Iba a ver cómo lo estás haciendo pero Instructables está caído.
Hoy estoy intentando meter bootloader a otro 328P y , cosas del destino, me está dando problemas. Dentro de una o dos horas me pongo de nuevo (tengo que bajar a cambiar unas luces del coche antes de que anochezca)
En mi caso el problema del bootloader lo resolví buscando la hoja de datos del chip del mega, para ver a qué pines arduino corresponden los pines del atmega MISO, MOSI, SCK y creo que SS, que son los que en el UNO van al 13, 12, 11. Lo documenté , y para variar, no lo encuentro. Tengo guardado de hace tiempo un esquema de conexionado correcto en Fritzing, que creo que lo bajé de Instructables, pero en ningún momentó se me ocurrió comprobar si las conexiones del esquema eran las que hice. Lo que sí recuerdo era que en vez de usar los pines 13,12... del mega se usaban 53, 52, 51 y creo que 50. Como no podía ser de otra forma, tenía conectados (llámalo pereza) los cables al Mega desde hace un mes, pero , oh Murphy, el viernes me hacían falta para un protoboard y los desconecté.
En cualquier caso, dentro de 1 o 2 horas me pongo de nuevo a la tarea, a ver si solucionamos el tema