everytime my users try uploading a GIF file, the quality is bad. And its sometimes blurry or random colors.
example: http://www.deanrussell.net/gallery/displayimage.php?album=topn&cat=-35&pos=6
on the left a blur of red sometimes appears on that gif.
any ideas?
That's likely a feature of the theme you are using. Switch to classic and see if it goes away. You can remove the feature by editing the style.css for that theme.
remember that GIFs only have 256 colors, so the quality can not be much better by design. This is a limitation that is caused by the gif file format, not by coppermine.
Joachim