In my case, it was literally a bad USB cable. Apparently it was right on the edge - adb logcat would work, but about half the time I would get this error when trying to push an app to the device.
Changed to a different cable, and everything was fine. The old cable was also very slow at charging, so I should have suspected it sooner...