You have a qualitative description of what happens, but let's break it down to a smaller scale. When we talk about "temperature" of something, we are really talking about how fast the molecules are moving around and bouncing off each other. "Temperature" is really "kinetic energy". And it turns out that there are other types of energy besides moving around in space -- molecules can rotate, they can vibrate, and their electrons can get excited and move around relative to the nucleus. Each of these energies can also be a "temperature", so you can have translational temperature (what we normally think of), but you can have rotational temperature, vibrational temperature, and electronic temperatures.
Molecules exchange energy with one another by colliding into each other. When they do this, they also distribute the energy between them. How often they collide determines how quickly the energy becomes uniform, and this defines how quickly they reach what is called equilibrium. When all of the different temperatures are the same, the state is in equilibrium and we don't need to worry about keeping track of all of the different types of temperature. For most of the processes that would occur in an engine, there is more than enough time to reach equilibrium and so we don't need to worry too much about non-equilibrium effects.
Now, in chemical reactions, molecules break apart and form new ones. If the new ones have less energy, the difference in energy is released as heat. If the new ones have more energy, the reaction requires adding energy to make it happen. Obviously engines get hot, so the reactions in them release energy and we harness that energy to move the vehicle.
So, molecules break apart. And they break apart when they start vibrating so hard that the bonds between the atoms cannot hold them together anything. The only way to make the molecule vibrate is to have another molecule collide with it, with enough energy and an efficient enough transfer of energy to start the vibrations. And the energy has to be high enough that the vibration makes the molecules fall apart.
By changing the amount of fuel in the mixture, you are changing the types of collisions that can occur. And it's not exactly straight forward, but some molecules are better at exchanging energy with others. To make the fuel molecule fall apart, they need to collide with other fuel molecules with some energy of with other oxygen molecules with more energy. If you add more than the usual amount of oxygen (run lean), you also need to make that oxygen hotter so the molecules have more energy when they collide and can make the fuel vibrate hard enough to fall apart. Conversely, if you run fuel-rich, you have more fuel molecules that can collide with one another and fall apart, but fewer oxygen molecules for them to combine with and give off heat. This (and some other effects) makes the final flame temperature lower.
Based on some extended conversation on the question, let's put this all back into the context of an engine. For a direct-injection gas engine, the air is sucked into the cylinder, the piston compresses it, and then fuel is sprayed into the cylinder. A spark plug then triggers a spark in the chamber. This deposition of electrons gets the fuel-air mixture molecules all excited -- it actually ionizes the air (strips off electrons from the molecules) and this all adds a bunch of energy to the molecules. This energy is the initial energy required to start the combustion.
For a fuel-lean condition, I said it takes more energy to start the reaction and I phrased it in terms of a higher ignition temperature. The ignition temperature comes from that spark plug (for a cold engine -- hot engines will also contribute heat from the cylinders themselves). For normal operating conditions, spark plugs provide more than enough energy to ignite. As the operating condition gets leaner, the spark plug provides the same amount of energy -- but it is still enough energy to ignite. Eventually, for lean enough conditions, it won't be enough energy. This is a lean misfire.
Diesel engines work differently. For sake of argument, let's stick with a direct injection again. The cylinder fills with air, the piston compresses it, and the fuel is injected. There is no spark to initiate the reaction though. Diesel engines rely solely on creating high enough pressures to ignite the mixture. High pressure means high density and that means more collisions to spread the energy around (molecules don't need to go as far to hit one another). At any rate, the same ideas apply. In lean conditions, it would require a higher pressure to ignite. At ideal conditions, the engine compresses more than is exactly required, so when it runs fuel-lean, it still has enough compression to ignite. If you go so lean that the compression isn't high enough anymore, you will again get a lean misfire. Glow plugs can help all this by heating the cylinders and helping to add heat to the mixture and get the reactions going.
In either engine, once they have been running for awhile, the cylinder walls heat up and it requires less input (from sparks or from compression) to make the reaction occur. But for cold engines, it needs that initial energy deposition to get the reactions moving along. Many ECU's are set to burn fuel-rich when the engine is just starting because it is easier to ignite; as they heat up, the mixture becomes more lean and reduces emissions and fuel consumption. You may be familiar with manual chokes on things like lawn mowers -- the choke is what changes the fuel-air mixture and to get the motor started, you have to set the choke to be fuel-rich.
For those interested, based on the discussion we had in the various comment threads, I went ahead and gave a concrete example of how/why temperature can increase when the flame is fuel-lean. The conversation in chat is bookmarked here.