I am exporting 1920 x 1080 clips out of CS4 AE as cineform avis/P4K444 and putting them onto a Premiere timeline. They look fine in AE and they look fine in Windows Media Player, but not on the Premiere timeline.

On the Premiere timeline, they lose just enough resolution to look soft.

Is there a simple reason for this?

Don't want to state the obvious, but I need to ask, have you selected "Desktop playback quality", or "Desktop playback fast" from the Cineform menus?

Try looking at it with VirtualDub if you want to see the quality.

"Desktop playback quality", or "Desktop playback fast" only affect Desktop playback (i.e. WMP.) However the Draft mode (vs High quality) within Premiere's playback settings will request half res. decodes.