You say you've tried it on two flavors of Windows. Was that on two different physical machines or are one or more of the OSes virtualized?
Two different physical machines, one with USB 2.0, and one with USB 1.0.
Is there a USB hub or KVM between the Leonardo and the computer or is the Leonardo plugged directly to one of the computer's own ports (the "root hub")?
Plugged directly to the USB port.
If you manually reset the board does the LED "breathe" for several seconds? Once it stops breathing does it start blinking with a period of two seconds?
No.
Do you have any shields or other electronics connected to the board?
No
Can you try uploading and manually resetting the board? Time it so you hit the reset button when "Compiling sketch..." in the status bar is replaced with "Uploading...".
I tried this and got the same error message.
Thanks so much for taking the time to look into this. I'm excited to start using the Leonardo - feels close...
- Rick