The key to the paradox is the famous fact that "viscosity is independent of pressure". The usual heuristic explanation is based on the elementary kinetic theory of gases. Viscosity is due to momentum transfer across streamlines. The crude analogy is of a food fight between passing trains. The transfer of material will speed up the slower train and slow down the faster train. In a thinner gas, a given volume of gas will have less momentum transfer from a nearby volume, but it will receive momentum transfer from a greater distance, due to the greater mean free path of the gas molecules in the thinner gas. Anyway, this means that very fine particles can be taken aloft in a thin atmosphere just as easily as in a thick atmosphere. Note this only applies to fine particles. Gum wrappers would not blow around in a Martian wind, because the atmosphere doesn't have enough mass density, and in this case our intuition about thinner and thicker air is correct.