I had this problem when I first installed my ATI 5870 a number of months back. Check your ATI Catalyst Control and under AA Mode check to see if it looks like this.
If it does change it so it looks like this.
This is what worked for me, hopefully it will do the same for you.