In adults, losing teeth is an unmistakable sign of bad health. General access to dentistry has reduced the frequency with which we experience it, but in the same way that our bodies instinctively know that smooth skin is healthier than zits and abcesses, they know that if you're losing your teeth, something is very, very wrong. We explicitly connect toothlessness with powerlessness, both in expressions like "has no teeth" and in the fact that only very old people are generally seen going without. The tooth dream - stress connection seems reasonable to me, since long-term stress is associated with poor health and risk of illness. Without having to unduly anthropomorphize the subconscious, I think it's reasonable to suggest that we might view failing health through this instinctual lens.

I've heard that people with eating disorders frequently have tooth dreams. This is consistent with the ideas above, even for ego-syntonic disorders like anorexia nervosa. You might have a social/moral/virtue framework that makes starvation desirable, but that's not going to be able to undo the genetic programming that's causing some parts of your brain to say "panic!" Among people who purge, of course, the teeth really are at immediate risk. I don't know whether we make the vomiting - tooth damage connection instinctively, but there's a good chance that someone has explicitly attempted to put the fear of god into the subject about tooth loss. Add this to the fact that people who purge usually have bulimia, which is more often ego-dystonic, and it makes sense that they will have bad dreams more directly related to a real feared consequence.
Note: This is not to imply that people who have tooth dreams are likely to have an eating disorder as well! Rather, this association provides a field in which to test the suggestions I made in the first paragraph.

Finally, did you ever stop to think about how damn weird teeth are? I mean, you're this squishy, watery thing, and yet you've got these hard, white bits inside your head! What the devil are they doing there? The whole inside of your mouth is pretty crazy, come to think of it. Tongue?