Nick,
To understand this phenomenon we need to consider what the propulsion systems actually do. In the case of both turbojets and turbo-props, the first step is the conversion of chemical energy in the fuel into thermal energy. The efficiency of this process varies with inlet air temperature and RPM. The colder the incoming air, the more efficient the thermal process will be. Although it might be tempting to imaging that thermal efficiency also increases with increasing RPM, this is not entirely true. Engines are designed to be most efficient at cruising RPM. For a turbojet this is typically in the 85% to 95% RPM range. Thermal efficiency declines as RPM moves above or below this band.
The thermal energy must then be converted into thrust power. This process is most efficient when the aircraft TAS is very close to the speed of the jet exhaust or propeller wake.
In a turbojet, this second conversion is carried out by the engine and propelling nozzle. In a turboprop it is carried out by a power turbine and the propeller. So the efficiency of this process in a turboprop depends to a great extent upon the efficiency of the propeller. These are designed to be most efficient at relatively low altitudes and speeds.
The overall efficiency of an aircraft is the product of the efficiency with which fuel is turned into thrust power (thermal/propulsive efficiency) and the efficiency with which that power is used to push the aircraft forward (TAS
rag ratio). So to achieve the maximum overall efficiency, aircraft must operate at the altitude producing the best combination of thermal/propulsive efficiency and TAS
rag ratio.
Engines are designed to be most efficient when in their cruise condition, which for a turbojet is typically in the 85% to 95% RPM range. So turbojet aircraft are designed so that the thrust in this RPM range matches the drag when cruising in the cold air at high altitude. At lower altitudes the denser air makes the engines capable of producing too much thrust. So RPMs must be reduced below the most efficient range. So jet aircraft flying at low altitude have high fuel consumption rates because their engines are operating below their optimum RPM range.
In turboprops, although the colder air at high altitude improves thermal efficiency, the higher TAS at any given CAS, reduces propeller efficiency. At high altitude the losses caused by propeller inefficiency outweigh the higher thermal efficiency provided by the colder air. This problem is further compounded by the fact that these engines are designed to run in their optimum RPM range when cruising at relatively low altitudes. So at higher altitudes the lower air density requires them to run at RPMs above their optimum range.
Or more simply, turbojets are designed to be most efficient at high altitudes and turboprops at low altitudes. So turbojets at low altitude and turboprops at high altitude, both burn more fuel because they are outside of their optimum conditions.