Debian Jessie – Cannot Install OpenJDK-8-JRE-Headless

This Friday I saw that I had 2 held back packages for some reason when I ran apt-get upgrade, so naturally I did what any inexperienced sysadmin would do and uninstalled the packages in the hopes that I could simply re-install them and the problem would be solved.

Little did I know, I just made the situation worse. When I tried to reinstall openjdk-8-jre-headless, I got this:

$ apt-get install openjdk-8-jre-headless
Reading package lists... Done
Building dependency tree
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 openjdk-8-jre-headless : Depends: ca-certificates-java but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

I tried to upgrade the mentioned package manually, but to no avail.

$ apt-get upgrade ca-certificates-java
Reading package lists... Done
Building dependency tree
Reading state information... Done
Calculating upgrade... ca-certificates-java is already the newest version.
Done
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.

Looking around I saw no mention of a solution to this exact error anywhere.

I use ElasticSearch on the server, which I restarted, but I should've expected that it wouldn't start up at this point. So now I'm without Java and my users are without search. What is going on and how can I fix this?