Likely you have a combination of two related problems.

firstly as you know frame-based movement doesn't offer constant speed movement, the better way is to use time-based movement, there are plenty of resources about this.
Basically rather than moving X units each frame, instead move X units each second -> Find the time passed since the previous frame and the current one (in seconds), multiply that value by the amount you wish to move (time_passed * velocity).
You can easily accommodate accelleration too, but like I said plenty of resources available.

Secondly with bezier curves you typically don't get constant speed, often the animation will slow down on the curvier parts and speed up on the straighter parts. To fix this you need to re-integrate to t, where t is time.
There is loads of info on the net but I recommend you begin by searching the forums here a GDNet.

Hope that was some help :)