What you're missing is that there may be multiple copyrights that apply to any particular piece of recorded music. In particular, there's the copyright covering the song itself (i.e. the notes written on paper), and there's the copyright covering the recording (i.e. the actual performance that you listen to). As far as I can tell, he paid for the song itself. He wasn't paying for the license to distribute a "low-res" version of the original recording — he was paying for the right to record his own versions of the songs.
This is why it's OK to sell your own performances of Beethoven's music (which has long been in the public domain) without paying anyone, but you can't freely copy a Vanessa Mae CD and hand it out to people on the street. There's no copyright to the song itself anymore, but the modern recording is still protected.
A photograph is more like a recording than it is like sheet music. If I happened to be standing right next to the photographer and intentionally snapped an almost identical shot half a second later, he couldn't sue me for infringing on his copyright.
If he had significantly transformed the tune itself, he wouldn't have even needed to pay for that, but AFAICT he produced faithful Nintendo-style performances of the original songs. That's why he needed to pay the rightsholder for the song.