Enquanto você mudou a bateria do CMOS, ela pode não ter saído por tempo suficiente para redefinir tudo. Algumas placas-mãe têm um jumper que pode ser removido ou um tipo de interruptor para redefini-lo. Caso contrário, remova a bateria do CMOS e deixe-a fora por algum tempo. Além disso, você testou a nova bateria do CMOS para garantir que está retirando a tensão adequada? Geralmente substituindo a bateria CMOS corrige problemas do BIOS, por isso estou surpreso que não neste caso.
Alguma coisa está aparecendo no monitor? É possível que o BIOS esteja carregando, mas a tela não está funcionando? Apenas um pensamento ....