I figured that the "not below 5000' " rule was more about the constant power changes, climbs descents and manouvering in the training area and was a simple explanation given to students in preference to a
proper explanation.
As others on this thread have noted, the person giving the explanation probably wouldn't know why themselves and couldn't work it out.
I teach the guys to lean as soon as you are established in steady cruise, be it 500' or 10,000'. Every flight manual I have ever read gives fuel burn figures based on a properly leaned mixture.
Sunfish:I have never
ever seen an Ops manual (read many and written a few myself) even
suggest that aircraft should be planned, let alone operated, at full rich all the time.