If a reboot doesn't clear them, you might have to go into Menu, Settings, Applications, Manage Applications, and select the All Applications tab. Look for Gallery, Media Content, and Media Container Services, then clear Data and Cache if anything in there for all. Ignore any warnings that data and information will be lost.
Reboot your device and wait for the sd card to remount and your Gallery should be fixed. It can take a while to reindex your Gallery pics if there's a lot of stuff on your card.