There's a lot of possible reasons for videos to not show up on the albums. A good way to check is convert a test file (something short, 2mins or so) with your settings and slap that on the SD card. If it doesn't work, well, just change the settings. Not sure about the framerates, but generally, I use 23 (default is 20), which should be fine to not mess around with. The 3DS can do 30fps though.
Some videos converted from rather difficult formats (like QuickTime's MOV or RMVB), even though converts just fine, don't play on the 3DS. I think it's the codec, but not really sure. A sure-fire fix for this though is to convert that video into something simple, like AVI (Xvid or DivX) or MPEG and then convert to a 3DS-friendly format.
Also, something I do that tends to "nudge" the app into prompting a Data Management update is to go to Settings, Copy files from SD to System Memory, but then cancel it. When I go back to the album, it usually pops up. Usually. Also, it helps to scroll to the earliest parts (leftmost side of the scroll bar).