In music, there's a difference between holding the copyright for the music, and the copyright for the recording. And it's absolutely possible to write a cover,

In music, there's a difference between holding the copyright for the music, and the copyright for the recording. And it's absolutely possible to write a cover, but where the music sounds different than the original version. People that do this don't have the copyright for the music, since the cover would not have existed were it not for the work by the original artist. That said, Coulton's version is very different, and probably could have led to some interesting legal arguments had it been challenged in court. But it's probably very relevant that Coulton first represented it as a cover, and that the entire reason his version (pre-Glee) became famous is because he marketed it as a cover.