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.
josto, can you send the status messages after a failed upload attempt (turn on verbose output in preferences first)? I'd have to see more to be sure, but your timing problem theory may be correct. Some hubs (and, by extension, the root hub in each computer) introduce their own delay when a USB device is trying to enumerate. If nothing else, you should be able to manually reset the Leonardo and get a successful upload every time.