Perhaps you need to disable auto-reset on the Leonardo. See: http://arduino.cc/en/Tutorial/ArduinoISP
"Note for Arduino 1.0: you need to make one small change to the ArduinoISP code. Find the line in the heartbeat() function that says "delay(40);" and change it to "delay(20);".
"An Arduino board serving as an ISP to program the ATmega on another Arduino board. On the Arduino Uno, you'll need to connect a 10 uF capacitor between reset and ground (after uploading the ArduinoISP sketch). Note that you need access to the reset pin on the target board, which isn't available on NG or older boards.