Why are multiple oxidation states useful for a catalyst?
The answer has a lot to do with "what is a catalyst in the first place?"
A catalyst is a compound that can affect the rate of a chemical reaction
by providing an alternative and lower energy profile or pathway. That is, 
it is a substance that makes it so that A -> B at a lower energy cost. But
it only has an effect on the rate of the reaction. That is, it only changes
the cost of the activation energy. It is not related to the thermodynamics
of the process and hence, the final product distribution. That is, if the 
above process gives 90% B via a non-catalyzed pathway in 4 days, then a 
catalyst will help you get 90% B in say 4 hours.

Okay, so a catalyst affects the transition state and activation path. How
does it do this? Typically, by complexing one of the reagents. Complexation
by transition metals affords access to a wide variety of oxidation states
for the metal. This has the property of providing electrons or withdrawing
electrons from the transition state of the reaction. That is, if the 
transition state is electron rich, then the transition metal might hold 
some of that electron density and those prevent too much from building up
on the reagent. This would then facilitate the reaction. Or the transition
metal might undergo formal oxidation/reduction to achieve electron transfer
to a substrate, thereby allowing a reaction to occur. This is "complexation
and electron storage" taken to the extreme but is a common mechanism in
organometallic chemistry. Indeed, a variety of catalytic pathways rely on
a two electron transfer between the metal and the substrate (e.g. 
hydroformylation). It is the ability of the transition metal to be in a
variety of oxidation states, to undergo facile transitions between these 
oxidation states, to coordinate to a substrate, and to be a good 
source/sink for electrons that makes transition metals such good catalysts.

Of course, this is for transition metal complexes. Most industrial used 
catalysts are the transition metal in a bed, as a metal or bound structure.
The above considerations are important but also the physical properties of
absorption/adsorption and the electron band structure of the material.