Acabei de me deparar com este problema com o mais recente libreoffice numa máquina de produção.
LibreOffice 5.1.6.2 10m0(Build:2)
Para corrigir:
sudo apt -y install libreoffice-base
Isto irá instalar todos os requisitos para o libreoffice, incluindo o java-jre