EDIT: To solve backward normals, (in edit mode) select Mesh -> Normals -> Recalculate Outside. This will recalculate all the normals so they point outward, but only works on a fully manifold (completely enclosed) mesh.
EDIT: In your case, it looks like you have some coincident faces (two faces that share some or all of the same surface area), and several n-gons. The part of the leg on the bottom right is probably an n-gon that just doesn't look like it. You may have two vertices very close to each other that look like one vertex, which would mean that this face is attached to 5 verts, when it looks like only 4.
To solve most of these problems, remove doubles. This will combine any vertices that are so close to each other that they look like one vertex.
As for the coincident faces, you'll have to be really scrupulous about finding out exactly which vertices each face is composed of. You can select a face, Delete -> Faces Only and then rebuild the face the way you want it.
=== original answer ===
Standard polygons have 3 or 4 sides. In some versions of Blender, non-standard polygons (sometimes called n-gons) don't have their centers marked (as with these examples).
N-gons also don't subdivide the same way that other polygons do in Blender. If you subdivide an n-gon, then the new vertices just become part of the perimeter of the n-gon because they n-gon doesn't need to subdivide (and the algorithm doesn't know how to subdivide n-gons). This is why you just see the number of dots around the edge increase.
To solve this problem, you'll want to make the n-gon into a set of standard polygons (3 or 4-sided), which can sometimes be difficult, but is always possible.
Hope that helps!