I am not 100% sure about this but we are doing something very similar, and this works for us.
Is the a4j:commandlink in the context of a form object (i.e surround your entire table with a a4j:form)?
Hope this helps.
I was about to send a quick response to the effect of "sure, I'm not that dumb", when I realized that I'm wrapping it with a "h:form", not a "a4j:form". Once I changed it to the latter, it worked perfectly.
You'd think there would be some runtime validation (optional, perhaps) to confirm the correct components are being used.
Actually we have been bit by that several times in various combinations of components where it was not properly enclosed in the required parent component.
A design time validator would sure be a nice addition, providing some form of warning when the correct components are not being used.