I think the problem is related what your fuses settings are requesting from your ATmega chip....
Some of the fuses define where the ATmega gets it's clock signal from... in the case of the lady ada guide, afaik she'll be assuming that you're getting your clock source from a 16Mhz external crystal - because this is the standard set-up for an Arduino board.
This means that your newly programmed ATmega chip is waiting patiently for an external clock source -> and unfortunately, until you give it one it's not going to play ball.
If you are suffering from the situation described above, you'll be given messages about 'no signature' and fuses will be automatically reset each time you try to reprogram yr ATmega.
For a while I thought I'd fried a lot of my ICs but as soon as I set it up with an external clock source all was well.
(For a nice way of discovering fuse settings try out: http://www.engbedded.com/fusecalc/