Samsung SGH-E635 / SGH-E630
I was having the same problem, same exact phone, found your post a few weeks back while trying to find the answeron-line. I found nothing and just could not figure it out. Until Friday night at dinner I was messing around with the Messages menu ... try this ...
2 - Picture Messages
3 - Outbox
How many do you have? I had tons. I'd cleared every other folder, but apparently when you upload photos to your on-line album, a copy is saved in the Outbox folder in your phone's memory. Clear those and you should be fine.