Without knowing your exact comp settings and parameters for opacity and colors nobody can tell you much. Typically one would work in 16bpc or even 32bpc to reduce artifacts, but even then accumulated transparencies may cause quantization and banding. That's just how it is.
16bpc 32bpc? im new to all this... :s
Without seeing a screenshot of your project or a detailed description of your workflow I can only guess. Opacity changes do not create pixels that are not already there. You may have your Composition Panel set up with a zoom factor of more than 100%. You may be seeing banding because of subtle color differences. You may be seeing the transparency grid.
Try this: Create a new composition using one of the Composition Presets like HDTV 1080 29.97 (my favorite because you have fewer problems with motion artifacts at 29.97 fps than you have at any of the lower frame rates). Check your zoom factor by hovering over the Magnification Ratio Popup at the bottom left corner of the composition panel and set it to 50% for best viewing on a standard monitor or Fit up to 100%, then set your Resolution to Auto, use the eclipse tool to create circle as a shape layer. Move the CTI to 1 second. Hold down the Alt/Option key and press "t" to reveal the opacity property and set a keyframe. Move the CTI to 2 seconds and change the opacity value for the shape layer to 0. Preview your animation. You should see the shape layer smoothly fade out. If you want check the transparency of your project you can turn on Reveal Transparency grid using the icon just to the left of the composition view selector. One more thing, ONLY the Active Camera view will render in your final project. The other views are only there for convince in setting up layers in 3D space.
If that works for you then everything is normal. You just need to figure out what is different in the composition that is giving you problems.
Thanks! That worked perfectly,. not sure what was wrong with the original composition, but for now its all good!