That could be done with Flash, Cinema 4d (or any decent 3D program), or After Effects. The smoothness of the floating type suggests that it was done with script, not keyframes. That is unless someone has a lot of time on their hands. I'm thinking Flash that is exported out to video, because some of the masking is jacked up. A typical result of using Flash and not knowing what you are doing.
Kind of nice effect, but the video gets boring fast. I couldn't make it all the way though it... there's just not enough going on to hold my attention. The floating text starts off interesting, but then gets old fairly quick. Maybe there was just too much of it? Did they have to spell out all of the lyrics? It's like they ran out ideas of what to put on screen so they kept repeating themselves.