¿Estás seguro de que el paquete se llama "openoffice.org"? Prueba lo siguiente:
Cita: sudo apt-get remove --purge openoffice*
De todas maneras, al instalar OpenOffce3.1, si lo haces mediante APT, te desinstalará antes las versiones previas que puedan causar conflicto. Y, ¿por qué no lo haces de manera gráfica con Synaptic, si en consola no te sale?