You have to recalculate the normals first. When you check the Display normals as lines option in Mesh Display panel you may see that there are some parts, where normals are directed in a wrong way.
Enter the Edit Mode, select the whole object (press A), and then press CTRL+N to recalculate normals. You can also do the same thing from the tool shelf on the left.
Now all the normals are heading the right direction, as you can see in the picture below.
With the normals recalculated you can easily paint on the model entering the Texture Paint mode in 3d view, or Paint mode in UV/Image Editor.
Remember that after you paint a texture, you have to save it, in other case it won't be visible after opening a blender file next time. When you see the 'star' symbol by the Image option it means that the image is not saved.
Hope I helped you.