I have a simple mesh, fully triangulated, closed surface, parented to an armature with "Bind to: Vertex Groups" selected. There are two bones, and a vertex group named like the child bone, which contains a couple of vertexes. The weight paint looks fine (surfaces around grouped vertexes are red, rest is blue). Seems fine to me.
However, the mesh doesn't move if the child bone is rotated in Pose Mode.
Am I missing any of the requirements? Given how often questions like this pop up, I think a comprehensive list of conditions that need to be fulfilled for skinning would be very useful. I'm not even sure if triangulation and a closed surface are required in recent versions.
I uploaded my file here: https://drive.google.com/file/d/0B3uTFOmcBwRQajBzdkY4QUpUejA/view?usp=sharing
Edit: Recreating the armature fixed it. Is there anything special about the first bone that is created? I'm still not understanding what is going on.