Make sure to select the correct sub-set of Windows Media, e.g. WMV 9 Screen, to retain full RGB ranges.
Actually I already tried that and while it did fix the background issue, it made the rest of the video look bad. From what I've read its not designed for highly animated videos, which mine is, so even at a higher quality it seems to stutter and the images appear to be at a lower color depth.
Maybe I'm setting it wrong?