ImageMagickが吐いたgifのサイズが大きすぎるという現象が
起こっています。
やはり特許の関係でだめなのでしょうか?
GDはどうなのでしょうか?
また圧縮ができるこういったソフトはないでしょうか?
このURLにあるように現在配布されているImageMagickはLZW圧縮がOFFになっているようです。
http://www1.plala.or.jp/fukafuka/install/image_magick.html
ふかふかの部屋 - Install Memo - ImageMagick
configure に --enable-lzw をつけて再コンパイルすれば圧縮が有効になります。