depends, if your making a video playback device from scratch why would you choose the arduino in the first place?
what I am saying is that unless your a sheild designer for arduino by the time you get the storage, decoding, and output sorted out for any flat out non sh.. video, get the thing made and then plug it into an 8 bit external micro just to hit the play button, you might as well toss something in there to do it all ... good example would bet a SBC like the (ugh I hate saying this) PI, or a dirt cheap celphone you can root and plop an app on it.