Paint is pretty great but if it's not working out for you, try exporting a movie as a Filmstrip and painting in Photoshop. A filmstrip opens in Photoshop as a series of frames in a column, with each frame labeled by number, reel name , and timecode.
You can break the filmstrip file into any number of smaller files by setting the work area to a different portion of the composition before rendering each portion.
When editing a filmstrip in Adobe Photoshop, use the following guidelines for best results:
You can paint on the gray lines dividing the frames of the filmstrip without damaging the file. After Effects will display only the part of each frame that lies within the frame border.
You can edit the red, green, blue, and alpha channels in the filmstrip file. Use only channel #4 as the alpha channel.
Do not resize or crop the filmstrip.
Flatten any layers you add in Adobe Photoshop.
To render, modify, and re-import a filmstrip:
Choose Composition>Make Movie.
In the Render Queue window click the Output Module template
Choose Filmstrip from the Format pop-up menu. Specify the rest of the settings you want and click OK and Render the Filmstrip
Open the Filmstrip in Photoshop and paint on the frames
Save the file
In AE, go to File>Import>File and choose the edited Filmstrip
Drag the Filmstrip to the New Composition button in the Project Window
Treat the Filmstrip like video footage