When you reboot your phone, there is a separate, background process that scans your SD card for media. I think it's called "Media Storage." It then builds a database that is read by the gallery.
Keep in mind that this background media scanning process sometimes takes a LONG time to run. It blindly looks through all your SD card files and directories looking for suitable media... mp3s, video files, etc. Depending on what's been modified on your card, it's a long process.
Give your phone a few hours... without rebooting or remounting your media (which will restart the process). Then see if they appear in the gallery. If not, make sure your SD file system is not corrupt, and that you have no bad media files that could hang up the scanning process.