Passei pelo mesmo problema e o terminal acusava com tudo instalado - mas nao funcionava.
instalei o synaptic, procurei o "ttf-mscorefonts-installer" e realmente estava instalado...
a solução foi clicar com o direito e pedir para reinstalar a aplicação. No caso pede todos "aceites" normais e passa alguns minutos baixando fontes. Ao final tudo foi instalado e as fontes aparecem perfeitamente no BrOffice.
Espero ter ajudado os próximos usuários do Ubuntu 11.10.
Abraços