You said you used Arduino 0010.
I've had problems with device signature with 0010/Atmega8/PC WinXP/Parallel Port Programmer. And another problem: the bootloader delayed 10minutes.
But with the same hardware configuration and 0011 version to burn bootloader works fine.
Can you try the 0011 to burn the bootloader?