I have recently started getting the “This accessory might not work with your phone” warning on several things (cables, car chargers) that used to work just fine with the phone.
Is it possible that one of the software updates made the phone “pickier” about what would and wouldn’t work?
It could but could also be the battery is beginning to show it’s age and the phone is not seeing what it takes as the correct power response to the cable.
The phone is pretty new (like 7 months), so I sure hope that’s not the reason!
Are these Apple cables or at least ones that have the “Made for iPhone” logo?
It’s possible there is some gunk in the connector port keeping the cables from making a secure connection. Use a can of compressed air to blow out the port or use an unused toothbrush to gently brush it out. If the problem continues, take it to an Apple Store.
This has happened in the past. If you’re using accessories that aren’t officially licensed by Apple, sometimes they stop working.
Cynics will say this is Apple’s way of making the producers of those devices pay to license, but it could also be that those devices don’t actually meet the spec, and Apple certainly isn’t testing to make sure they keep working.
I don’t know how recently you’ve updated your OS but Apple started restricting some third-party peripherals with iOS 7. Optimists would say they did this to secure and unify the Apple experience for their users. Cynics would say it was to shut out third-party manufacturers who didn’t pay licensing fees and to protect their market share.
Count me as a cynic. I’m all for capitalism and all, but Apple charging $40 for a short 30-pin to Lightning adapter cable that they deliberately imposed on their customers and, more importantly, are made by Chinese orphans and probably cost Apple no more than 35¢ each in bulk is ridiculous. 
In regards to the OP, did you replace your cigarette lighter USB adapter? It must provide more than enough amperage to your iPhone or you’ll get that warning constantly.
You can get officially licensed ones from Monoprice and Amazon for $9. Both companies have pretty low margins, so I doubt they cost as little to produce as you suggest.
Lightning cables actually do a surprising amount of processing in the cable. It’s not just a passive piece of wire connecting things.
Now ya tell me*!*