Ok so quick update, I took everything apart and reassembled it out of the case and the cpu fans are now starting fine.
What fixed it was putting the fan control in bios to DC from PWM. I don't know when the bios switched to that because I'm sure I did not change it.
Oh well, Glad I got that fixed. Thank you for your help!