I prefer to requeen this time of year (late summer to early fall).  It allows the new queen to get settled in and ready to go in the spring.  That way you don't have to worry about whether or not she will be up to the job of spring buildup.  If you buy queens from a known breeder whose stock is selected for traits you like, such as gentleness, you will have a known quantity in the spring.  
If you wait you may have a failing queen in the spring and no way to replace her until the breeders start shipping in April.   I suppose this is more of a problem for me in California than it would be for you in Minnesota, where spring doesn't start so early.  (Spring for me is February.)
I don't like to let the bees make their own queens because they tend to get a little too defensive after a couple of generations in my experience.
Another advantage of summer/fall requeening is that the queens are less expensive and often better mated than the spring queens.  
Michael
----------
From:   Mark J. Vogel[SMTP:[log in to unmask]]
Sent:   Wednesday, August 20, 1997 11:13 AM
To:     [log in to unmask]
Subject:        The best time to replace queen?
 
I have two hives with queens that are two seasons old.
They seem to be doing fine, but my understanding is the
queens are past their prime at two years. My question is
should I replace them now with new queens with the risk
of losing them if we have a severe Winter, or should I
wait until Spring to replace them?
 
Mark Vogel
Rockford, MN USA