Let me start by saying THANK YOU VERY VERY MUCH for all your quick responses and advice! I tired everything you said, and the camera is okay, the segments doesnt do anything except make the tree more detailed (more branches etc.), but when I tried to check ANTI-ALIAS, I noticed it was greyed out. I then remember I has set the Brush mode to MESH, and when I set it back to BRUSH, ANTI-ALIAS was available again. I rendered it and it looked pristine, but too pristine. The bump map and displacement is gone, and only exisits when the brush is set to Mesh. As you said in another post, PaintFX is a POST process and is drawn on top of everything else, so my theory is that this "mesh" that is generated by PaintFX, is not getting to go through the renderer's Anti-Aliasing pass, and is applied afterwards, without any anti-aliasing. The flickering then would actually be aliasing, which actually helps our quest, because now we know what we need to find: A way to anti-alias a PaintFX brush mesh when it is processed after the Maya Renderer's Anti-alias pass already did its work.
Now the question is... how do we do that?
Hmmmmmmm.......... There's always more questions.
Thanks alot for all your help so far,