The 3800 series should be able to handle AoC pretty well. I've heard that some ATi cards have problems with AA though. Maybe you should try turning that off. You could try updating your drivers too. Also, list the rest of your computer specs because it could be that you don't have enough RAM (or fast enough RAM) or your CPU is too slow.