I seem to have fixed the problem.
I rebooted into original Sansa firmware (using Power and left buttons pressed together). I backed up everything on the Sansa first. Then I went into settings and formatted it. Then I used the Rockbox utility to reinstall from scratch. Everything worked then, though it was obviously all new settings and so on.
I also was able to get my original settings back in an interesting way. Just to see what would happen, I copied over my backed up .rockbox folder. When I did that, the errors came back. Not a surprise. Something was bad in that folder. Then I went and ran the Rockbox installer utility again. This time it went quickly and it seems like it just reinstalled whatever file needed fixing and left the rest. Now it's working just as it did before with all my settings but with the error fixed.
So if you have this problem I recommend first going in using the Sansa firmware option and backing things up. Then try just running the Rockbox utility on it and it may just fix what isn't working. If not, then do the whole process and format it, reinstall from scratch, copy over your backups and then run the Rockbox utility one more time.
Mikhail, I'm not sure why you assumed it's a hardware problem without ruling out a bad file somewhere in the .rockbox folder or something. Although I'm not saying you're definitely wrong. It's possible that I fixed it for now but if the memory is bad perhaps it will go bad again in time?
In the meantime, things are working as normal again and hopefully will stay that way.
If anyone has this problem, please don't jump to the conclusion that your hardware is bad. It may just require a reinstall of Rockbox like I did.