I was unfortunate enough to have the oppoiste order of installs: the four packages, and then URE. That meant URE's install failed, and I was left with apt complaining about a broken system. To get out of it, I used dpkg -r to get rid of the offending four packages, and then installed ure. Of course, then apt began moaning that libreoffice- java-common was broken, but I removed that and the packages I had depending on it.
Obviously I would like them back, but libreoffice is working just fine without them. Just wanted to put my workarround up here in case anybody else had the same bad luck as me.