four different sets of batteries all prompt the same "change batteries

You're probably right. One set of batteries might be bad, but three sets probably aren't. Now you need to look to the other end of the electrical connection: The battery contacts inside the camera.

Traditional use-once batteries leak, and the residue from the leak can stay on the battery contacts. The electrical connection can also draw salts out of the air, which crust on the contact points. Try cleaning both the contacts on the removable plastic cover, and the contacts inside the battery compartment (if possible). I like to use mildly abrasive tools like brass wire brushes, pink pencil erasers, fine grades of steel wool (#000 or #0000) or even dry toothbrushes; these remove dirt and scuzz without doing much harm to the metal contacts themselves. Make sure that the camera isn't plugged into an electrical charger while you're doing this. You might try wrapping a little fine steel wool around a pencil eraser, then sticking it into the battery compartment and rotating the pencil several times to clean/polish the metal contact. If you want, you might twist a paper towel up into the compartment to pick up any loose bits that are left behind. Then reinstall the batteries, and see if that solves the problem.

In any case, it's safer for the camera if you use the rechargeable NiMH batteries, rather than alkaline; they're much less likely to leak.