Might be too early to say, but I think that clearing out the internal storage has perhaps solved the problem.
Connected to PC and went through deleting stuff that was obviously redundant and cleared out the download folder. Then I scanned and cleaned with CCleaner. Tried some music, and it was OK.
I've then copied the download folder back and tested again. Still OK.
Finally, I've re-inserted the SD-Card (not formatted), and tested again. Still OK.
So it COULD have been something present on the internal memory, but not the download folder or the SD card. I will keep an eye on this but hopefully that is the solution. If not, it'll be factory reset time (which I don't really want to do as I've got everything set up how I want it!).