Fortunately this error does not propagate any further. The central part of the paper (block identifier encoding, which already needed f(n) = sqrt(log n)) stays untouched.
Thanks to Jakub Opuszaski, from University of Wrocaw, for pointing out this error.
Another point raised by Bojian Xu, from University of Kansas, is not really an error but needs clarification. The problem is in Lemma 4, where we say that the bit vectors B^j are precisely those that would result if we built the wavelet tree just for L^j. This is not completely true because the local text can have a smaller vocabulary than the global one. In the extreme case one can have two partitions a^n and b^n, so that the local wavelet trees have entropy zero, but that require a whole root bitmap if they become a wavelet tree on a,b.
The answer is that those overheads add up to o(n log s) (s=sigma). Consider expanding the local wavelet trees before integrating them in the global one. Each unused symbol we add to the local wavelet tree converts a leaf into an internal node whose bitmap is all 0s or all 1s. With as few as log s new symbols we can already force the creation of the n log s bits. However, all those bits we add are runs of 0 or 1, and thus the (c,o) encoding of RRR reduces them to o(n log s) bits.