Thanks for all the answers!
As for the USBtiny, I know it works well, I've used it to program the 328 with blink (to test the board, and it works well), and to put the bootloader back.
And the chip does power up when I connect the USBTiny. Should I try to connect the usb at the same time (to provide another power source for the chip while programming it)?