Sounds like a 'scope is your best next step.
Computer recognition and USB cables are probably not an issue. From the avrdude errors you quoted, the problem will be between usbtiny and your circuit, or in your circuit.
Another idea... The usbtiny by default has some series resistors in the communications lines. Those are really only for use with the POV project and should be shorted for general programmer use. (This improves the source/sink current and hence rise/fall time, especially important if the lines have more capacitance such as in the 10pin ISP cable with its interleaved ground lines.)
Also, does your circuit have anything else attached to the MISO/MOSI/SCK pins on the atmega16? If so, it might be interfering with programming. Atmel has some guidelines to prevent interference, but sometimes there are still problems. The most certain approach is to disconnect those pins from normal circuit usage when doing ISP.