You'd rather use a Cell that generates a title="" attribute.
The reason for the title="" disappearing is that CellTable "redraws", and does so by generating the table and using innerHTML, and thus replacing the whole DOM subtree.
In GWT 2.5, you'll be able to provide your own CellTableBuilder (you'll probably subclass the DefaultCellTableBuilder) and add a title="" attribute on any <tr> or <td> you'd like.