I just noticed the "plugged in, not charging" today for the first time on my Surface 3. Not sure if that's always been the case, as I've never paid attention. I restarted, same message appeared. After about 20 minutes it showed "plugged in, charging" even though I didn't do anything to the physical plug. Not sure what's going on.
One thing I do notice is that the charger isn't strong enough to charge the Surface while it's in use. At work, I'll often prop my S3 up and have a game open all day (I have the S3 set to not shut the screen off when on the charger) and it never gains battery during the day. It just maintains whatever battery level I was at in the morning.