Voltage Too High, Charging Paused - Galaxy Note / SII Problem
I searched a bit online and found that this looks to be more of a firmware problem than hardware or battery related problem.
Fix:
I could fix the problem by going to Developer -> Turning On USB Debugging.