Wow thats weird since the cooling fan is electric and not run by a belt. If I were you I would go ahead and replace the tensioner assembly. Its not real expensive and its good practice to replace the tensioner when you put a new belt on it.
How does the belt feel? Grab a hold of the belt (engine off of course 😛 ) try to twist it side to side. It should only be able to twist 1/4 turn at the most