Thank you everyone for your help. I have finally solved this issue, and I would like to explain the procedure to do the same.
Clear previous installations of gdal in your Ubuntu system.
$sudo apt-get remove gdal-bin
$sudo pip uninstall gdal
$sudo apt-get remove python-gdal
Download GDAL source from this link . You can browse and download one of the stable releases.
Now, do the system install by these steps.
$ cd gdal
$ ./configure --disable-netcdf --disable-fortran --with-python
$ make install
This installs GDAL with python bindings in your ubuntu worstation. It will have HDF4 file support for processing MODIS data.
Please note that you need to use Python 2.7.6 (I have tested using this python) to process HDF4 files. You cannot use iPython to process HDF4 files.
P.S. : Thanks to my dear friend Florian M. Savoy who assisted me in solving this problem.