I looked it up and it appears that there are some dependencies missing in the classpath. The link leads to github issue that pertains to Selenium, but since Appium is based on Selenium, I think it would be relevant in your case. Basically it says that “Selenium requires guava library to be in classpath.”.
To avoid dependency issues, I prefer to work with Gradle. I assume that you are working with Eclipse since the tutorial you linked to makes use of Eclipse.
In Eclipse → File → New → Project → Gradle Project. Name your project and click finish. Eclipse will initialize Gradle project for you.
Then open the file titled build.gradle and paste the following code into the file:
apply plugin: ‘java’
sourceCompatibility = 1.8
testCompile group: ‘junit’, name: ‘junit’, version: '4.12’
testCompile group: ‘io.appium’, name: ‘java-client’, version: ‘6.0.0-BETA2’
Then right click on the project in the project explorer → Gradle → Refersh Gradle Project. That should fetch all the dependencies and allow you to execute your tests.
Let me know if it helped.