I had the same issue and I would like to share my solution to the problem :

1) First make sure that you have the necessary hdf4 drivers installed :

****apt-get install libhdf4-dev** 

**apt-get install proj-bin** 

**apt-get install libproj-dev** 

**apt-get install libgdal-dev** 

**apt-get install gdal-bin**     (Thanks to user @mdsumner for this)

2) Then there seems to be a issue with the pyModis package itself as explained by Luca here : 
https://github.com/lucadelu/pyModis/issues/29#issuecomment-104800294

So I removed pymodis and installed the new version directly form the Github site, run the following command 

**sudo pip git+https://github.com/lucadelu/pyModis.git**

and then to be sure run an upgrade


and then TADA !!! The HDF4 problem should be gone when you import pymodis.

Hope it helps
~cheers