I have run into this same problem, while writing a lejos based codebase for the ev3 plott3r bonus model. After much thought, and code inspection, and digging into my engineering controls text books, I think I know what the issue is.
PID loops need to be tuned for the process they are controlling. The ev3classes library is using the NXT regulated motor class, and there is two sets of PID parameters, one for holding a position, and one for regular movement. The code shows that authors have gone through and tweaked the values a number of times, but the root cause of the problem here is that there is no one set of numbers that will work for all robots: You might be able to get a decent starting point, but really, if PID control is going to be used it has to be adjusted for the specific motor in the specific robot -- i.e. a large ev3 motor driving a wheel for a large robot will need very different parameters than a medium ev3 motor directly driving a lightweight arm.
There are literally thousands of papers on tuning PID parameters, but there are some straightforward rules to get a good starting point, and this is something that should probably be run for every motor on every robot if PID control is to be used.
First, the I and D parameters should be set to 0. Then, adjust the P parameter until the step response is reasonable without too much overshoot. If you measure the time it takes for the motor to reach the desired speed (or position), that becomes a feed into the I parameter: in general, you increase I to get rid of offset (P control will always settle on a value that is not quite the set point, until you add in I). Finally, the D parameter can be tweaked to balance acceleration against how much overshoot is used.
(check out the PID article on wikipedia for a reasonable overview of PID control and tuning. - http://en.wikipedia.org/wiki/PID_controller
So, the long story short, the issue is that it is impossible to have a PID controller class with fixed PID values as written that will work properly for every motor and every robot. The base set up will work for some motors and robots well, and on others, there will be overshoot and other problems. I don't think that this is really a race condition for the most part: overshoot and oscillation are typical for a poorly tuned PID control loop. Certainly starving the PID control loop from updating often enough will cause a problem, but really there is plenty of power on this controller even running java for the threads to run. In the NXTRegulatedMotor class, The control loop thread is set at the highest priority, so it will tend to run properly unless the entire processor is at 100% cpu usage.
I don't know enough about how lejos works... yet. It looks like there is a decent reusable structure there, and I would like to figure out how easily I can write different regulation module, while using the same basic regulated motor interface. At the very least, I would like to make the PID values adjustable. Taking the next step, it would be possible to build in a self-tuning mechanism that could be used on a robot to adjust it's own parameters, and allow other types of regulation to replace the PID control. I believe that for the plott3r robot, for example, PID control is probably overkill: there isn't much inertia or load in the system, and so a simple power + tach count check should be enough to drive it at a reproducible speed.
Those are my 2 cents on the issue. I will post back if I come up with anything useful, but comments would be welcome.