If paint effects is assigned to a 3d curve then it will follow the curve normal( which is based on the local curvature and is poorly defined... unless "useNormal" is on, in which case the normal is simply a constant direction ). It needs a curve on surface to understand a surface orientation.

If you paint onto the poly surface instead of doing attach brush to curves it will work OK. (this will create a special curve on poly that currently only paint effects uses)

Also in Maya8.0 code was added that will convert the 3d curve into a curve on poly when you do "attach brush to curves" as long as you have both the surface and the curve selected. It looks for the nearest points on surface. You can also have multiple curves and surfaces selected.

The curve on poly used by paint effects is currently not directly editable the way a curve on surface is. You can still edit and key the translation of this curve however. Here is a mel script that makes the path editable by turning the 2d curve into a 3d curve where the x and y correspond to u and v on the surface. The curve appears near the origin in the x y plane. Not as nice as curve on surface editing, but still usable.