There are two extremely common causes for weirdness in video rendered from AE:
1) Using interframe-compressed video like mp4, AVCHD,MPEG or h.264 (pre-CS5 versions)
2) Using Open GL to accelerate renders. NEVER use it. It's so bad that Adobe dropped Open GL-accelerated rendering from the newest version of AE.
Either of these apply? If not, use the following link to provide useful diagnostic information:
http://forums.adobe.com/thread/961743
Dave LaRonde
Sr. Promotion Producer
KCRG-TV (ABC) Cedar Rapids, IA