Make sure the highlighted layer also has the checkbox filled. Sometimes it looks active because its highlighted, but the actual layer box isn't checked.
When you first start the sculpt, the initial layer is highlighted but not checked by default. I think this is to prevent accidentally moving the center when you first try to set the sculpt up.
Also sometimes the active layer may be selected at the same time as a non-paintable medium object (mirror, etc), and the program won't know what you are trying to paint.