The OS X issue was with the same bit of code, but technically it was a different problem since it was platform specific. The Linux problem here is also platform specific, but I haven't figured out why yet. The code in question is basically just a call to SDL_Sleep(), and it hasn't changed in years. It used to work fine, but now it doesn't. There hasn't really been a SDL change that I can find, so it may be an issue with newer kernels or something. There are numerous ways to do a non-blocking sleep on Linux, and I've tried them all, but always get the same results.
The OS X fix was to use a "cpu whore", which basically amounts to an empty while() statement that just eats up CPU time to perform the same functionality. That is supposedly an accepted fix on OS X, but it's a really hacky way to go about fixing such a problem.
The Linux "fix", at the moment, is to just use v-sync and let the video drivers handle the FPS cap for you. That way we don't have to be directly dependent on X to solve the problem, since the drivers do it internally. Where most people get tripped up there though, is that they have v-sync disabled at the driver level, which means that the game's call to enable v-sync is ignored by the drivers. So just make sure that you aren't overriding v-sync at the driver level and that should take care of it for you. Your FPS will be limited to your refresh rate, but you won't get the slowdown any longer.