I just got a new song, but I already had the Song Reward for it.

In Co-op Shows, you can play songs you don't own if they're selected by other players.
As a result, you may obtain song rewards for songs you don't yet have.