The Thrust Specific Fuel Consumption (TSFC) is actually worse at higher altitudes - basically the compressor has to 'work harder' with the thinner air. The lower temperatures do help, but not enough to offset the loss of compressor efficiency.
As PDR notes, it's the lower drag at high altitude that normally makes it more efficient.
Note also that cruising at a higher altitude doesn't always give better fuel burn - there are optimum cruise altitudes dependent on aircraft weight - go lower or higher and you'll burn more fuel at the same cruise speed. This is all programed into the Flight Management Computers to assist the crew in optimizing their flight plan.