Am not really sure, but logically, both fans should turn on at the same time to give maximum airflow to the entire GPU Card at whatever settings it is on.
Most likely both fans are controlled by the same circuit (component) in the GPU card which is the same circuit (component) that GPU softwares uses to control the fans. I would physically check the connections between the GPU fan and GPU Card or Cowl (covering). Possibly when you cleaned the GPU card you may have damaged one of the fan's cables or shorted something out if your cleaned the GPU with power on. Another possibility is the fan that activates later on is going bad. Maybe you may want to replace that one fan or both if it is sold as a set.
Your bearings may be going bad in the fan. They can slip until it is going fast enough to start it moving. When you clean fans, you need to hold the blades stationary. If you clean with with air and let that air whip the fans around real fast it can ruin the fan. It could also be that it is just worn out. If that card is under warranty the maker should replace fan for you, if you check as elstaci said and find it isn't a connection issue.