Do stars twinkle when seen from Mars' surface? Mars' average atmospheric pressure is 0.006 atm (0.088 psi). Is that enough to make fixed stars on Mars' night sky twinkle? Do we know an air pressure or density limit for that?
Following howstuffworks and my own metereological intuition, the key effect for stars to twinkle seems less the pressure or size of the atmosphere but rather if different layers (usually of different temperature) exist, and if the gradiant between the layers is steep enough.
Light passing through zones of differently dense air on its way to the observer lead to small (time-dependent) distortions occuring for instance over warm asphalt of a road. Here, the light travels horizontally through the atmosphere, rather than vertically like in the case of twinkling stars.
I like to imagine the parcles of hot, less dense air rising from the ground as the bubbles in a lava lamp.
In the case of a hot road, a few dozends of meters (on Earth's surface) is enough to cause the flickering of e.g. cars at a distance.
The visible image then becomes somewhat blurred, and since the air is constantly (and irregularly) moving upward over the hot street, it looks as if the air is flickering.
Applied to your question: I know that dust devils are likely occuring on Mars, which need atmospheric instabilities in order to exist, so I would assume that there are indeed atmospheric conditions where one could observe twinkling stars on Mars.