I had the same issue and I would like to share my solution to the problem :
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
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 !!! Thethe HDF4 problem should be gone when you import pymodis.
Hope it helps
~cheers