Mine only says not charging occasionally when I have it plugged in via USB, never had a problem with my mains charger, though it is one from my old N86 and I hammered the securing clips flat as I ripped quite a few ports out of various N86's, all of which were replaced at Orange's expense : )

I'd say try using a different charger, if that's no different try via USB.
If you presume it's software, re-flash your device (if you've done an OTA update you should probably re-flash it as a matter of course).
If that doesn't cure it, back to NOKIA it goes.