This is a long complicated post so, be forewarned:
mp4 is a container, not a video format.
People need to spend some time learning about what a container is and why it basically means not much of anything in the long run. A container... well, it contains streams of data, and when people think "video" files they're actually audio/video files.
The oldest container is still AVI, which by the very acronym means Audio-Video-Interleave, a Microsoft created format that's nearly 20 years old now. The problem with that container is because of its age it's never been able to support anything more than basic audio and video streams inside it.
Nowadays, that's not enough, so there are a multitude of containers out there: mkv (Matroska), mp4/m4v (the "official" MPEG4 standard container is mp4; m4v is an offshoot that allows for some different aspects), ogg (can be audio, video, or both), mov (QuickTime, fairly old to be honest, almost as old as AVI is), rm/rmvb (Real Media, plain and simple crap to be honest), and a few others.
Think of it this way: say you have a case that can hold CDs or it can hold DVDs. They're both the same size discs, hence the case - aka the container - is pretty much static, but the contents inside the container can be either format, you can store CDs or DVDs, or you can even mix them up and have combinations of both.
That's what a container like mp4/m4v does as well. You can put audio streams (aac, mp3, ogg, wav, etc) and video streams (h.264, Xvid, Divx, MPEG1, MPEG2, AVC, etc) inside, one or the other or the most common type which is both, hence the modern "video file" which again is most accurately an audio/video file.
But, there's other stuff you put inside containers nowadays since they've matured way past what the AVI container is capable of. You can put multiple audio soundtracks inside the container, you can add multiple subtitle tracks in it, custom fonts for those subtitles, multiple language files, and even chapter markers so you can skip chapters in a video file
just like you do on the original DVD or Blu-ray. Hell, you can even name the chapters just like they're usually named on the liner notes of DVDs and Blu-rays, and your media players will usually display the chapter names when you jump around the files.
There's a ton of stuff you can do these days.
The one thing you shouldn't do is blame a device for being incompatible with video (again, audio/video) files that you've created designed to be played on another device like an iPhone or iPod touch. There really is no one perfect container for every device, nor is there one perfect format for the audio and video streams that will end up being compatible with everything
That's just not going to happen.
The Nook Color has very specific capabilities that happen to be fairly common, actually, especially for mobile and portable media devices like iPhones, iPod touchs, Archos tablets, etc. That's why learning more about video (ok, last time: audio/video) encoding is a good thing - being less ignorant makes things easier on everyone, especially ourselves.
The preferred video format for the Nook Color is by using h.264 as the encoder and using a profile that encoder follows to create content, known as the Baseline profile. I'd be willing to bet that the poster above probably encoded his files using the High profile that h.264 also supports, but the Nook Color itself doesn't. The Nook Color is quite a capable little video playback device as noted by the clips I've created that I've been told play back flawlessly with no problems at all.
Apple doesn't have some special hold on "mp4" files - I have a handful of "mp4" files on my hard drive right now that no Apple product can play except the actual computers so, that's where the poster above is a bit off-course, laying blame on a container that doesn't deserve it, much less the Nook Color either.
All I can offer is this: if you're not happy with the Nook Color, send it back or return it for a refund or sell it.
I don't even own one yet but I've used one and I got no beef with it. I took a few minutes to find out what the device is capable of playing back according to the specs in the User's Guide, then I created video files that play on it and will play on any iPod touch, iPhone, iPad, HTC HD2, Archos tablets, and even my 6 year old Dell Axim X51v PocketPC without breaking a sweat, with great image quality and great sound too
There's absolutely nothing wrong with the Nook Color - the issue lies in the format and encoding parameters used to create the videos taking into account that the iPhone and iPod touch and iPad use very different hardware. Apple doesn't do anything
that is "standard" except a standard that they define for themselves and their own hardware.
Too many people approach this encoding thing backwards...