I suggest the use of "jhead", found at
http://www.sentex.net/~mwandel/jhead . Under Debian, running "apt-get install jhead" will download and install this for you.
This kind of behavior is often seen on Macintosh files (at least under OS9 and earlier) where a thumbnail preview is generated and stored in the first part of the filename. From your post, it sounds like other information is also being stored in the first part of the JPEG file.
By stripping the thumbnail and other data out of the image file, you can sometimes get a substantial decrease in image size.
This is not a problem under GIF because it is a simpler format that does not allow you to put this extra info into the file to begin with.