I think the method has too much implementation complexity and too narrow applicability to be worth it.
Though the paper is correct to point out the importance of solving the tridiagonal-symmetric eigenproblem in the course of solving the general-symmetric eigenproblem, it neglects to mention that the "frontend" procedure between these two scenarios (Householder tridiagonalization) already requires $\mathcal O(n^3)$ flops. This will dominate the overall complexity of the general-symmetric problem, no matter how you solve the inner tridiagonal problem.
Similar difficulties exist in the context of Lanczos algorithms for large sparse/structured eigenproblems. Although they project down to tridiagonal systems, these instances are much smaller in size than the original sparse system. So solving tridiagonal eigenproblems still doesn't drive the overall cost, compared to the cost of the "full-size" matvecs and vector operations incurred by the Lanczos iterations themselves.
The tridiagonal eigenproblem just doesn't occur very often by itself, instead it's typically preceded by other (more expensive) preprocessing. So it would seem that fast algorithms are probably not worth the effort here.