Sound like thats the problem right there. That fan has to come on when the A/C is on, it takes a little while for it to turn on after you start the A/C but it should be running when A/C is on. Check the fan before replacing it, feed 12v to the connectors and see if it spins. If it does then it's the relay.
I didn't know if that model car had a auxiliary fan, if not I would have told to go there first. Sorry