Not sure whether you could find your answer since this post seems old but i was facing the similar issue when the network is slow or when you are on VPN. Basically, there is a default timeout of 5 seconds inbuilt into the appium server which waits for the adb commands to respond back and on slower networks, the command response takes more than 5 seconds.The ay to fix this is as follows:
In your Desired capabilities, set the capability as below:
final DesiredCapabilities capabilities = new DesiredCapabilities();
capabilities.setCapability("deviceReadyTimeout","10");
where 10 is timout in seconds for getting the device ready
