Which version of the Arduino software are you using? Some are known to have
broken ArduinoISP setup.
Is the 328 in the Duemilanove one with a Duemilanove bootloader?
It is a 168 in both in the Duemilanove and on the breadboard, but the one in the Duemilanove has the bootloader and the ArduinoISP sketch loaded on it.
How did you install ArduinoISP onto that chip exactly?
Same as loading any sketch, plugged my Duemilanove in via USB selected the board type and com port in the IDE and uploaded the sketch to the board.
What board setting did you use, did it really succeed without error?
Yes, had "Arduino Diecimila or Duemilanove w/ ATmega168" selected, and had no errors and am able to upload blink etc with no problem.
Which board do you have selected when you try programming
the bootloader onto the 168?
The same "Arduino Diecimila or Duemilanove w/ ATmega168"
Have you really forgotten decoupling capacitors on the 168? No chip can
be expected to work reliably without them.
No, have a pair of 22pF caps on the breadboard, as per the diagram.