Thank you for your reply!
I tried removing the album art, both via MP3 Tag and via the files in the album folder on the memory card itself. It stilll doesn't seem to want to play...
Something else I've found is that I can find the song's file when just searching through "files" on Rockbox, but if I search by Artist, Track or Album, the file doesn't appear in those lists at all.