Highly charged dust grains in plasma discharges reside at the sheath edge, where the ions stream toward the electrode at speed approximately c(s). Above a critical pressure P(crit), the grains lose their kinetic energy and reach a strongly coupled crystalline state, but for P <P(crit) the grains acquire a large random kinetic energy and act like a fluid. We show that the dust heating in the fluid phase is due to an ion-dust two-stream instability, which is stabilized at P >P(crit) by the combined effect of ion-molecule and grain-molecule collisions.