Java on Linux insufficient memory even though there is plenty of available memory being used for caching

Have a look into the jvm min max memory, do you use any web server? Look into the number of treads, memory settings for it- for Tomcat most of them are @server.xml. Look into Java Mission Control http://www.oracle.com/technetwork/java/javaseproducts/mission-control/java-mission-control-1998576.html to get extra insight. Linux usually keeps more memory to be ready when requested. For Java on Linux only something like JMC can help you get an idea on what's going on. Have a look in the standard output from the JVM.

Seems like the issue has nothing to do with memory, but with process limits. The user I'm running the process as had a really low process limit set to 1024.

ulimit -u
1024

and the thread count of all the proceses run by this user is close to that:

ps -eLf | grep 'myuser' | wc -l
1022