What are your sequence settings compared to your AE comp settings? What
format and codec is used for your preview files? Are you exporting with
the option to use preview files (CS4)?
I'm using 720x480 at .9 pixel aspect in both AE and in Premiere.
I'm not familiar with the option to use Preview Files, where is that? (I'm in CS4).
I don't know where the codec info for the Preview Files is either so I can't answer your question.
Scroll down to the end of the Wiki article, it is all spelled out there.
I gave you the links in post #1.