Here's how I do it:
1. Allok Video Splitter - cut out segment I want
2. Macromedia Flash - import avi, export into a New Folder as a PNG sequence (resizing images to make them smaller)
3. Macromedia Fireworks - Open, select all frames, check "open as animation" box. Resize gif, add borders, use Image Preview function to export at a good size.
You're problem seems to be you're taking a video file directly to the gif making process, which doesn't really work well.