PID to control turntable speed?
Ooooh fun! An audiophile question!

Now, a lot of this depends on the particular turntable you have. 

Anyways, since you stated that your turntable is belt-driven, by far the easiest way to reduce your velocity flutter is to simply increase the mass of the record platter.
Realistically, if the record platter is less then 1/2 a pound, I would honestly recommend you simply get a better turntable. 

Most turntables tend to have AC synchronous motors. Now, using an arduino, you're not likely to be able to get significantly better velocity flutter without replacing the oscillator crystal on the arduino.

Realistically, for an application that requires a purely analog velocity servo, "21st century technology" really has nothing to add. Throwing a microcontroller at the situation just increases the complexity, without actually improving the eventual performance. I can pretty much guarantee a well-designed simple analog PLL-based velocity loop will kick the MCU-based velocity controller's ass unless you invest many hundreds of hours into the software in the micro, and even if you do, you'll at best achieve parity. The MCU won't be able to do better, merely just as good.

Realistically, I think the most readily achievable improvements to your setup are going to be mechanical. Reworking the electronics will be both very involved, and not likely to yield improvements. 



Many (somewhat crazy) Audio nuts have built custom turntables with platters that can weight 50+ pounds!
Browing the google image search for "Audiophile turntable" is always amusing.