Can you confirm which version of Appium you’re using? For maximum compatibility, it’s recommended that you use Appium Server 1.8.1 (note: this is not the same version as Appium Desktop, in which case you’ll need 1.6.3).
Here are some troubleshooting tips that might be helpful: