Syncs but won't always charge?

iPhone sometimes will charge but typically will not. The charging indicator shows, but over a period of time the battery will gradually decrease. New cables and chargers have been ruled out. Even when it does not charge, I have been able to do a full sync on my laptop without an issue in iTunes.

Sometimes if I take the cord out and plug in repeatedly a few times, the device will indicates charging AND actually charge.

Took to Apple. First time they erased and cleared all the settings, and the problem persisted. Going back again and they did a firmware restore this time (still haven't restored from a backup) and no luck.

Connector port is clean each time and different Apple folks indicate the port appears fine. They also ran battery diagnostics each time and comes back fine.

Help!