Была та же проблема, когда полностью вычистил 3.6 и установил 4.0 либру.
Потом прошерстил список установленных пакетов из архива с офсайта (откуда и устанавливал) и обнаружил помимо libobasis4.0-kde-integration_4.0.0.3-103_i386.deb пакет libobasis4.0-gnome-integration_4.0.0.3-103_i386.deb (а я использую kde на убунте). Удалил. Стили снова можно менять.
Видимо по умолчанию идут настройки gnome.
Это все я к тому, что название ненужного пакета может быть и не «libreoffice-gnome».