We investigate the influence of counter-ion valency on the flexibility of highly charged flexible polymer chains using molecular dynamics simulations that include both salt and an explicit solvent. As observed experimentally, we find that divalent counter-ions greatly reduce the chain persistence length, lp, in comparison with monovalent counter-ions. On the other hand, polyelectrolyte chains having trivalent counter-ions adopt a much more compact conformation than polyelectrolytes having monovalent and divalent counter-ions. We demonstrate that the tendency of polyelectrolyte chains to become deformed by proximal high valence counter-ions is due to chain "coiling" around the counter-ions. In particular, we find that the number of contacts that the proximal counter-ions have with the polyelectrolyte dictates the extent of chain coiling. This ion-binding induced coiling mechanism influences not only the conformational properties of the polyelectrolyte, but also the counter-ion distribution around the chain. Specifically, we find that higher valent counter-ions lead both to a counter-ion enrichment in close proximity to the polyelectrolyte and to a significant reduction in the spatial extent of the diffuse counter-ion cloud around the polyelectrolyte.