Just found this from Exdous1999 and Baka no Kami: Tested and worked perfectly for me.
Messed around a little and finally found settings that work for making nookcolor compatible video. I used a converted called Handbrake which is available here: http://handbrake.fr/
If you need help using Handbrake check the user manual they have on the site.
Set the output container to "MP4"
On the video tab set the "video codec" to "MPEG-4 (FFmpeg)". Set the "Target Size" to something appropriate for the type of video. I find that 175MB for every 30minutes of video gives a good picture, so an hour long TV show would be 350MB a 2hr movie 700MB, etc.
On the audio tab highlight whatever is in the bottom box and hit the remove button. The audio turned out to be the problem the first couple of times I tried this, the audio on my original file had a sample rate of 48 and the NC wouldn't play it, when I lowered the sample rate suddenly the video worked. So, set the autotab like this:
Source: Automatic (or use the drop down to choose which audio track you want if the video has multiple)
Audio Codec: AAC (faac)
Now hit the "Add" button.
The only thing left is to set the destination for the final file. Browse to whatever folder you want, but be sure to use .mp4 or .m4v as the file extension, if you use anything else the NC will not recognize it as a video file even if everything else is right.
Now hit the start button at the top and go read a book while you wait for Handbrake to process the video.
Other settings may also work for video, but so far this is the only thing that worked for me, so it's what I'm sticking with.