Saving a flat-color animated gif but it's coming out with a dot pattern instead of solid color

What settings/methods are best for creating an animated gif with sharp image quality?

Here's what I'm working with: http://ift.tt/1vRMFG3

This graphic is for a high-end client so I want it to be as sharp as possible. I've tried creating the animated gif several ways and this is by far the best result I have.

Here's my approach:

save image as PNG
import into Flash to animate
publish as GIF image with the following settings: 'Optimize colors' and 'Smooth' are checked. Dither: Diffusion. Palette Type: Adaptive. Max Colors: 2500.

I would like the finished GIF to have a flat, solid color look (without any type of dot pattern on top) on the envelope. The seal needs to keep the gradients and I cannot nix the dropshadow either.