You are probably getting more colors in your output file than in the input. If you want to preserve the orginal color set, use nearest-neighbor sampling instead of other types of filtering such as used by default when resizing. If you are using the command line, try
convert image_in -sample WxH image_out
instead of
convert image_in -resize WxH image_out
The result might be more jaggy than you'd like, so it's your choice to trade off appearance for filesize.
EDIT: The question was edited after this answer. The added information indicates that the image is in JPEG format (so adding colors is probably not the explanation) and it contains a SWOP color profile. The profile could be large, and is preserved by ImageMagick. For details, type "identify file.jpg", which will give you among other things the size of the color profile. If you want to remove the profile, use the "-strip" option.