That probably explains it, I am in fact powering the servo with the Arduino (Arduino powered by the USB).
I have followed this tutorial Tutorial: Control de servomotores con Arduino - BricoGeek.com but there the servo is different and the Arduino is the Mega edition.
I will try with an external power source and let you know..
Thanks !