3d coat will be more than a vertex prog, it will be a "voxel" prog
(volumic pixels) ;)

Zbrush has a special mode for painting an object!
It's the "polypainting" mode http://www.zbrush.info/docs/index.php/Polypainting

It's the more easy, you have just to paint on the surface of the object
It's better if you export your model with big numbers of polys (for have not to subdivise in Zbrush)
from Moi in "Triangles Only" format Obj

Thanks for the suggestions, guys.

Yeah, if ZBrush has a flip function, I'll have to read up on it cause (obviously) ZBrush doesn't get much use with what I'm currently working on so my skills with it could certainly be better...

I'll look into the smoothing also.

-Will