Parallax Servo strange behavior

Hi all,
I'm really stuck with this and I could use some help an ideas!
I recently obtained a continuous rotation servo from Parallax (I think the model was "900-00008") for my project.
I drive the servo from one my Arduino Uno's i/o pins, using the standard servo library.
Originally I supplied power to the servo from the 5V output of the arduino board.
This worked perfectly. However to use the full power of the servo you have to supply 6V.
So what I did was, I powered up the Arduino from a 9V/3A external PSU, then used the "Vin" and "GND" outputs of the arduino board to source a small circuit with an LM7806 and a couple of capacitors, then supplied the 6V output of the LM7806 to the Servo. I kept the "signal" input of the servo connected directly to the arduino.
I expected things to work exactly the same, only this time with more power on the servo.
But the result was surprising:
When I activate the servo, I hear a quiet buzzing sound coming from it, like it is barely moving. It doesn't "kick", like getting stuck from heavy load, it's just looks like moving very very slowly. When I deactivate the servo, the sounds stop. And the weirdest thing is that, if I disconnect the signal cable of the servo, then servo starts to rotate at full speed for about 3 seconds!
To me it doesn't seem like a problem with the power supply of the servo. I checked the voltage and it is a stable 6V, and the power supply unit can provide enough current.
I suspect that this must be a problem with the signal. Originally I though that because of the 5V width of the arduino's pulse, this might be a problem. But then I check on the datasheet from Parallax and I saw that it is okay to provide a 3.3-5V pulse, even if you power the servo with 6 Volts.
On a another forum I found someone that had a similar problem (Servo worked at 5V but behaved strange in 6V). They told him that probably the Grounds of Arduino and the Servo are not interconnected. That made sense because he was using a battery to power the servo.
However, I am using an external power supply and all circuitry has a common ground, so that wouldn't make sense in my case.
Can you please help me? In my project it's really critical to use as much power as possible, and I'm really out of ideas...
Kind Regards,
Giannis

So you have the Arduino ground, the servo ground and the external power supply grounds all connected together? They should be.

used the "Vin" and "GND" outputs of the arduino board to source a small circuit with an LM7806

use your multi meter and make sure that VIN voltage stays steady (doesn't drop or vary when the motor act oddly) and make sure you get 6V from the 7806 and not lower.

Basic wiring for a servo.

servo-wire.jpg

Thank all of you for the replies.
It turned out that the problem was related to grounding.
Although all grounds (external PSU, arduino, servo) were interconnected, it seems that the ground of the servo was taking a very long path, which was introducing a small but significant amount of resistance.
By connecting directly the ground wire of the servo into the ground of arduino using a short jumper solved the problem.
My mistake was that because I was using an external PSU (and not a battery) I assumed that all grounds are sufficiently interconnected, but it turned out that this was not the case.
I suspect that that one reason this may have happened is the fact I was extensively using the wirings of the breadboard, which may not be ideal for grounding.
Regards, Giannis