There is no magic here.
If you connect a wire from the battery to the fan positive, and leave the fan grounded to chassis, does it turn on?
Yes: Power feed issue. Check your power wiring and relay.
No: Your ground is bad. Either your ground feed from battery to chassis is insufficient (does the car start and run?) or the ground for the fan has an issue.