I think mine was fine with just being in the DCIM folder. If it is different, I'll update it here.
I can confirm Roger's observation in that all movies must go into DCIM\100NIN03. This subdirectory seems to be consistent even after reformats and photo app resets on the 3DS.

After creating a few more movies, 75 seems to be the best quality setting in SMM. It's an OK balance between video quality and playback speed. The 3DS still drops frames when watching a 24fps movie, but not horribly so. I also found that you may want to bump up the brightness a bit when creating your source material. On my iMac, the images looked to bright when converting a couple test clips from Godzilla 3D (an admittedly dark movie to start with), but looks great on the 3DS.