A troca da bateria não elimina o CMOS, a menos que o cabo de alimentação tenha sido removido e o tempo tenha sido reservado para a descarga entre a remoção e a substituição (não especificado em questão).
Você tem um monitor diferente para testar? Todos os sintomas que você descreveu podem ocorrer com um monitor defeituoso, que leva tempo para "aquecer" antes de ser exibido.
Por favor, teste com outro monitor. Se os resultados forem os mesmos, se você ainda não tiver feito isso, limpe o CMOS com o método acima. Eu acredito que o primeiro resolverá o problema.