OK, so you changed the battery whilst the message was still there, but sometime after changing the CMOS battery, you also also had no video output. Just confused me weather the video problem was intermittent or occurred suddenly.
Either that PC speaker isn't working (unlikely), or that
CPU is another component, which is hardly suprising based on the status of those fans. I've also checked your motherboard manual/spec, and there is no auxilery connection for your battery. This means at a minimum, your list of replacement parts includes two fans, a motherboard, and highly likely to include
CPU. Ouch!