I had this problem and tried every fix including; reset, cleaning, different chargers, soft re boot, airplane mode etc. It was driving me mad!
Apple telephone support couldn't help and it took loads of attempts to get it to charge until I found my own solution:
Plug in your charger to the phone and power supply
'Ok' the annoying message - 'accessory may not be supported'
Turn the iPhone off while leaving the charger plugged in and switched on
When you turn your phone back on having left it for a while the charge will have increased. Turn it back off and leave it for a while longer and it will be fully charged
This has now worked consistently several times - happy days!!
Not perfect as you have to switch your phone off but, it works!