Considering all you have done to fix it so far, it sound like an odd variant of the old bad song/playlist glitch. See this FAQ entry for a possible way to fix it.