Perhaps I have the date wrong, then?

I do remember the individual app backup+restore, which I would have done if I'd known that I was going to need it. But I didn't have any data I cared about (just my music, which was already in iTunes), so I figured I'd just reinstall the apps. I remember re-jailbreaking my iPod afterwards and trying to find an old version of Spotify to install online, but being unable to find a trustworthy source.