Android error: Failed to install *.apk on device *: timeout

What I usually do when I get this error is restarting the adb server by typing in the cmd:

adb kill-server

adb start-server

EDIT: With some never versions of the Platform Tools you can do this from the DDMS Perspective in the Devices Tab menu (near the Capture Button), click on Reset adb.

EDIT2: Also I found out that it is preferable to use the USB port in the back of your PC, since most of the front USB ports are low powered, and really seem to be slower when uploading apks on your devices.

Try changing the ADB connection timeout. I think it defaults that to 5000ms and I changed mine to 10000ms to get rid of that problem.

If you are in Eclipse, you can do this by going through

Window -> Preferences -> Android -> DDMS -> ADB Connection Timeout (ms)

I used to have this problem sometimes, the solution was to change the USB cable to a new one