I always used my Apple charger with my iPhone 5. Since the beginning I was occasionally getting a similar message, but it said more like that the accessory wasn't compatible when I plugged in to charge. Within about a month I started having problems with bad connection when charging. It got worse until it was almost impossible to charge.
I have had iPhones since the original came out in I believe 2007. I have upgraded regularly, and have had four iPhones on my plan for some years. The iPhone 5 was the first with the lightening connector, and it was the first that I had problems charging.
Whatever the reason for my charging problem, it caused me to switch to a Windows Phone, although I still have three iPhones on my plan.
Did you ever replace the cable the first few times you got the message?
Even Apple cables go bad, you're supposed to replace them at the first signs of problems.