Entre na BIOS, desconecte o cabo de energia e tente recalibrar a bateria, depois de ter feito esta etapa inicialize o Ubuntu com a bateria e veja se ele agora a reconhece.
Embora a bateria seja nova, o computador é bem antigo e pode estar com problemas para carregar a nova bateria ou não é totalmente compatível ...
PS: Eu recomendo que você atualize para a última versão 13.10 porque ele tem um kernel mais novo e seu problema já pode ter sido resolvido (Use a versão de 32 bits já que a versão de 64 bits é baixada por padrão).