Since replacing the 12 volt battery once seemed to produce a temporary improvement, I'd also follow that line of inquiry and check the voltage and, if possible, the capacity of the new battery. Maybe they didn't fully charge it before installation, and it went dead again?