Selendroid is not responding with latest version of Appium

I’m using the latest version of Appium for Windows (1.3.4.1) and Selendroid as the automation infra.
When trying to launch the my application Appium respond with:
info: [debug] Making http request with opts: {“url”:“http://localhost:8089/wd/hub/status",“method”:"GET”}

info: Error: Waited 20 secs for selendroid server and it never showed up

I tried to replace the Selendroid.apk from version 0.11 to 0.15 after reading there is a bug in version 0.11 but with no luck,
it still fails.

Any ideas how to solve this issue?