The thing to remember about transparent GIFs is that they don’t do transparency like Photoshop does. Photoshop can do variable transparency, where a pixel can have a transparency value between 0% and 100%. The way transparency works for GIF files is that one color value is transparent, and the pixels that have that color are 100% transparent. No feathering or anti-aliasing.
Since Photoshop normally uses anti-aliased/feathered/partially transparent edges, when you translate the artwork into a GIF only the color at the very edge becomes transparent, and you get all these dangling pixels that should have been partially transparent.
There are a couple of ways to get around this. One is to use the same background color in Photoshop as your web page will have. That way the one-color transparency will mesh better. The second way is to design all of your web graphics completely in Photoshop, and slice them up for output without using transparency (background colors included).
The third option is, if you absolutely need transparency on your image, is not to use GIF. Unfortunately, the only alternative is PNG with transparency (32-bit PNG), which IE6 doesn’t support.