PID tuning limitation
You may need to detune it (make the response more sluggish) at the higher speeds, or apply the concept of gain scheduling. It behaves now like the closed-loop gain is higher at low speeds, which will tend to reduce the stability. 

Real cruise controls are generally disabled at very low speeds anyhow, for safety reasons.