It is interesting that this topic is 2 years old and the problem is still ongoing with no solution ..
I got this problem today ,unrelated to video codecs though ,unpredictable ,it does get resolved with restarting AE ,sometimes with restarting my pc ,I have a monster pc with 4 processors, 8 Gig RAMs with the dual video card and I am only rendering 2 seocnds in the comp and getting this nasty message
NEED 2 FRAMES TO PLAYBACK !