Here's a more lengthy thread on the issue...
The stone skinny is here are the acceptable formats...
From the NOOKcolor FAQ:
"Your NOOkcolor supports the following video file formats: 3gp, 3g2, mp4, m4v; MPEG-4 Simple Profile up to 854x480; H.263 up to 352x288; H.264 Baseline profile up to 854x480
Your NOOKcolor will not support the following video file formats: Flash (Flv/swf); Mov/qt; AVI; MKV; Xvid/divx; WMV / VC-1; H.264 Main and High profile; and videos with a resolution higher than 854x480"
Check your video size, if it's over 854 the NC won't be able to play it, I had similar problems. I use MPEG Streamclip, a free program that has a number of adjustable settings. The MP4 with an H264 compressor works just fine for me.
Great program a lot of us are using is DVD Catalyst and you do want to use the 854 x 480 setting. This program has a lot of one button settings as well as the ability to modify them as needed. For instance it has a setting for the NOOKcolor and many many popular devices to convert to mp4 format.
I just converted a video to mp4 file with Format Factory and it worked with Format Factory 2.60:
Select All to MP4 under VIDEO
Click Add File and select a video format you want to convert.
Click Output Setting, click the box next to Default for Video Size, type 854x480, click OK, click Ok
When you are back at the main screen, just click START and you connect your Nook and copy the converted video file you just did in the Video Folder on your Nook.
Go to Media and just tap the video.
For video files that need converting, I've had good luck with RealPlayer. Use the iPod touch setup and edit the video resolution to 480 x 853 ... or if you worry about a precise 16x9 ratio, 477x848, but its not a difference I can see, just as DVDcatalyst noted.