OP, you asked, "Might unplugging then plugging them in again, rule out one potential cause?" Yes, maybe do that several times (with your system turned OFF!), then plug back in and turn on. This MAY "scrub" dirt or oxidation from pin contacts and solve the issue of a bad connection.
What IS plugged into that CPU_FAN header? What type of CPU cooler system do you have? IF it is fan(s), you can try this as a temporary testing step. Shut down your system and change fan connections so that the one that IS cooling you CPU is plugged into a CHA_FAN or SYS_FAN header, and a different case fan is plugged into CPU_FAN. Start up and watch the messages. If this still produces that error message, then the CPU_FAN header is NOT responding to the speed signal it receives and is faulty. On the other hand, if this results in NO such message from CPU_FAN, but you see NO speed reading available from the CHA_FAN or SYS_FAN header where you plug in the actual CPU cooler, then that cooler system is failing to send its speed signal back. When done, shut down and restore the normal fan connections while you figure out your next steps.