are you rooted?
you gallery should, by default, pull any images from your phone memory/SD card, such as "camera shots, all photos, all videos, all downloads, video"---do you have any extra Albums listed apart from those?
if you rooted and are running a ROM with a googlemaps file, chances are that file has all of the icons and is therefore showing up in your gallery.
i had the same issue happen to my phone when i installed a MarioLive wallpaper.apk and all of the little images then appeared in my gallery b/c they were downloaded to a file on my SD card. solution to that problem? moved the file from the root of the SD card to the MARIO.APK folder and didn't have any issue after that