Try explicitly installing the Python dependencies since "setup.py test" does not install them in a way that makes them available later.
diff --git a/.travis.yml b/.travis.yml
index 1cde8c4..12d08fe 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -64,6 +64,8 @@
       sudo apt-get install -y --force-yes libssl-dev/lucid
     fi
   - |
+    pip install -e .
+  - |
     coverage run --branch --source=OpenSSL setup.py bdist_wheel test
   - |
     coverage report -m