ATI cards have a few TODOs left, but they *work*. Composition works. 3d works well enough for things like scorched3d to work. Shaders don't work yet, but they don't work for *any* cards under Linux (the Mesa layers aren't stable yet: that's part of Gallium). (That the features list says MOSTLY for all of these simply says that the drivers are ready when Gallium is, AIUI.)
Of the r600/r700 TODOs on that list:
Video decoding using the 3D engine and UVD do not prevent video playback: they only mean that the CPU has to do the video decoding. If you could play back a video on a lesser card, you'll be able to play it back on r600/r700 right now. Shaders are awaiting Gallium. Antialiasing I don't know about; HDMI audio I don't pay attention to as I've got no hardware that cares about it.