I've seen even small stoves glow red-hot when they're opened right up.
As Deggs has said, you may need to introduce more air. I doubt if the house is quite that airtight though... unless it's very recent build.
I would look at the flue. I guess you have a 125mm or 150mm steel flue pipe coming away from the fire? Just a few inches above the stove is the place where condensate trickling down from above, settles and condenses. That creates a buil-up of ash and tar which will effectively choke off a stove.