Right. So I've finally got to the bottom of the problem: it was a botched in-place OTA upgrade.
My suspicions intensified after my Garmin Fenix 2 wasn't able to connect via bluetooth and after googling "Marshmallow upgrade issues". Anyway, a "Factory reset" fixed the issue.
Surprisingly, the reset did not return the phone to the original Kitkat; instead, the wipe process picked up the OTA downloaded 6.0 upgrade package and ran with it, resulting (I guess) in a "cleaner" upgrade.
Of course, this meant that the phone lost all the apps that I'd installed. But, freshly installed apps, including mine, work without any changes (i.e. there is backward compatibility). Whew!