Así parece. #include "jni_md.h" incluiría el archivo en el mismo directorio que jni.h , pero se coloca en linux carpeta.
En versiones anteriores de JDK, parece que ese archivo y otro estaban ubicados en include/linux carpeta, pero hay enlaces simbólicos a ambos archivos en include .
Así que puedes crear enlaces simbólicos a ambos archivos:
$ sudo ln -s /opt/jdk1.8.0_11/include/linux/jni_md.h /opt/jdk1.8.0_11/include/jni_md.h
$ sudo ln -s /opt/jdk1.8.0_11/include/linux/jawt_md.h /opt/jdk1.8.0_11/include/jawt_md.h
Editar
Como se indica en los comentarios de Absurd-Mind y Mikkel, también existe la opción de agregar esa ruta a las opciones del compilador del archivo MAKE:
-I$(JAVA_HOME)/include/linux/
No, esto no es un error. La forma correcta de resolver este problema es proporcionar -I${JAVA_HOME}/include -I${JAVA_HOME}/include/linux opciones del compilador. De esta manera, sus scripts de compilación seguirán siendo portátiles.
El OP enfrenta el problema en Linux, pero si alguien enfrenta este problema en Windows, agregue las siguientes opciones del compilador.
-I"%JAVA_HOME%\include" -I"%JAVA_HOME%\include\win32" donde JAVA_HOME apunta a su directorio de instalación de JDK, normalmente 'C:\Program Files\Java\jdk1.{7|8}.{}_{xx}'