Many airports have take-off weight restrictions. The mountains to the north west of Malaga would reduce the weight that could be lifted. But to be fair, 21˚C is not that much. However, a quick wizz to
aena.es (Spanish Aviation Authority's website) shows on most departures a climb gradient of 6% or so. And even the most asthmatic of aircraft should be able to achieve this. So I'd suggest that was a combination of wind, temperature, basic weight (was this aircraft fitted with a cargo door) and a deficiency of some description which reduced the weight lifting capability of the aircraft. The reason you were given was almost certainly correct and quite reasonably you were not given the full details. However, this is not the way you run a low cost airline. Fuel stops cost a fortune and waste the best part of an hour.
PM
PM