I understand that the heated intake air will burn more efficiently with the fuel and that's why recuperators increase efficiency.
Actually that is not the reason.
When applying a recuperator to a gasturbine design, the heat from the exhaust is used to warm up the combustor entry air, the effect is that in order to reach the same combustor exit temperature you simply need less fuel, that is the main reason why recuperated cycles are more efficient.
The part I don't understand is that if efficiency is going up, why isn't the power output also not increasing along with efficiency?
Why would power go up, it is expected to go down actually! The reason for this is that you cannot add more fuel to the existing design as that will cause the exit combustor temperature to increase, the turbine cannot handle those temperatures. So, with fixed turbine entry temperature you cannot add more fuel. What you do with recuperation is add more complexity to the cycle (heat exchanger, tubing, etc.).
Is there a limitation in oxygen rich air supply?
No, there is plenty of oxygen available, but you cannot use it because the temperature of the turbine would get too high.
Why does the gas turbine recuperator hugely increase efficiency but slightly decrease the peak power?
The first part of this question is already answered above, the reason for a decrease in power is related to the insertion of the recuperator. A recuperator is a heat exchanger and has pressure loss deltas over the 2 sides of the heat exchanger, pressure loss cause the output power to decrease.
This is best shown by use of a simulation example. Assume we have a turboshaft gas turbine without a recuperator and assess the performance. This is best done by sweeping the combustor exit temperature, this is then in turn used on a recuperated engine with and without pressure losses in the recuperator.
Below is a graph of such a simulation exercise in a gas turbine simulation tool. The three graphs from top to bottom show the specific fuel consumption SFCshaft, combustor exit temperature Tt4 and the combustor fuel flow Wf_b plotted against shaft power PWshaft. The red dot-dashed line shows the performance of a non-recuperated turboshaft engine. The blue solid line is an ideal recuperator operating without pressure losses and the black dashed line account for a pressure loss in the 2 recuperator flows.
From the graphs you see that the specific fuel consumption decreases when using a recuperator, this is clearly made visible in the fuel flow graph where the recuperated cycle requires less fuel. Furthermore, the pressure loss in the recuperator shifts the curve to the left, so less power is generated for the same turbine entry temperature sweep.