My machine is Ubuntu 14.04.4 LTS (trusty).
I had multiple Java installed on my Ubuntu machine so I decided to delete all of them according to this answer and install only Java JDK 6 (which is what I need to compile Android 4.3) using the command:
sudo apt-get install oracle-java6-installer
oracle-java6-installer is already the newest version.
It looks like not everything was dispatched utterly, but that's quite alright - the command you'll want is:
sudo apt-get install --reinstall oracle-java6-installer
This will forcibly reinstall the package, without trying to remove it by any other means.