Did you remember to use -kb when you added them? If not, CVS may have performed line-end conversion or RCS keyword substitution on them. The easiest solution is usually to mark them as binary
floss$ cvs admin -kb foo.gif
and then commit a fixed version of the file. CVS will not corrupt the new commit or any of the commits thereafter, because it now knows the file is binary.