Usually when you see that it is a current issue. The fans take more force to start moving than to keep spinning, and ususally the bigger the fan, the more force (and hence more current) needed.
Do you have more than one fan chained together on a single connector?
Try a different connector and see if that helps. As mpjesse said, it could also be a bad fan.