Enable verbose upload - that way you'll see what signature it's getting. 0x000000 = wiring problem or crystal not connected correctly; I'm almost certain that's what you're getting.
Are connections to the bare chip correct? That doesn't sound right at all.
The minimum for bootloading at 16mhz:
16mhz crystal on XTAL1 and XTAL2 pins.
Ceramic capacitor (of value specified by the crystal - 20pf is common) from XTAL1 to ground and XTAL2 to ground.
Ceramic capacitor, 0.1uf between Vcc and Gnd, and another between AVcc and Gnd. These must be located right next to the chip, and they must be ceramic caps, and they must be around 0.1uf.
AVcc should be connected to Vcc.
AREF should not be connected to Vcc.
To make autoreset (and hence programming over serial) work normally, you also need 10k resistor from reset to Vcc, and a 0.1uf ceramic cap from reset to the DTR pin of the serial adapter.