I don't think you did anything wrong. We have a test for this kind of thing in the A4J support module, so it should work.
However, since the error says that two components have the same exact client ID, it means we probably have a bug in either JSFUnit or the JSF implementation. See http://wiki.jboss.org/wiki/UsingComponentIDs for a discussion of JSFUnit and component/client IDs.
Which JSF implementation are you using? Also, which version of A4J/RichFaces are you using?
Here are the versions I am using:
I figured out how to make it work for the most part. I had to wrap my columns with <rich:columnGroup> the same way I did in the header facet.
However, I noticed that addUIData() added the ancestors (aka header facet) over and over again for each row. This could be an issue for other test cases.