What kind of new layer did you make? Which brush tool are you using?
Try making a solid layer in your composition, double-click it to open it in the layer panel and THEN start painting on it there. Paint effects only work in the layer panel.
If you're new to AE, you should really, really start here: Getting started with After Effects The resources on that page answer this question and many others you'll run into.
Yes, as Szalam says: The brush is only working in the layer panel (where you cannot see the background movie layer, but only your transparent layer).
Thanks very much for the answers. On a solid layer the paint brush work well. Thought it worked more like Photoshop layers but this is thifferent. Guess every paint stroke makes a new layer.
To learn to use Paint simply type paint in the Search Help field at the top right corner of AE. This will point you to a bunch of resources that will help you understand how to use the effect.
The second link on the page points to a very good introduction to Paint in AE by my friend Angie Taylor.