While mucking around with some examples, it seems like spark-examples jar is not being included in the distribution tarball. Also, it's not in the classpath in the spark-submit classpath, which means commands like run-example fail to work, whether a "distribution" tarball is used or a regular mvn package build.
The root cause of this may be due to the fact that the spark-examples jar is under $SPARK_HOME/examples/target while all its dependencies are at $SPARK_HOME/examples/target/scala-2.11/jars. And, we only seem to be including the jars directory in the classpath. See here for details.