The reason why the tooltip doesn't appear after updating the cell's text is simply that the node that originally had the event listener to display the tooltip is removed from the DOM and replaced by a new node without re-applying the tooltip functionality. There's just no way for a basic tooltip to know that it's original triggerer has been removed. Even using ace:ajax rendered attribute wouldn't work to update the tooltip in this case because the tooltip itself doesn't change so there's no update sent in the response that would re-initialize the tooltip.
Fortunately this can be easily fixed at the app level. Two ways are illustrated in the attached files welcomeICEfaces1.xhtml and welcomeICEfaces2.xhtml. In the first one, instead of an h:outputText, an h:panelGroup is used, which contains the tooltip itself, so when the panel group is updated, the tooltip is updated as well. In the second one, the issue is fixed by using the delegate mode. You simply wrap the table in an ace:delegate component and move the tooltip outside the table. Even if the content of the tooltip is static, delegate will work perfectly for this case too.
Attached test case that shows the issue. Note: The icefaces, ace, and compat, jar files need to be added into the war to run.
Steps: