Quite possible. It's also possible that Jobs & Page made all kinds of more or less random comments, and people remembered and retold the stories about the times they were strikingly correct.
I'd guess the truth is somewhere between the two.
You don't have to be precise to the milliseconds, you only have to be able to recognize 100 milliseconds, 500 milliseconds and 1000 milliseconds. The rest is guessing work.
It's the same thing with the width of elements on the web. Know what 10px is, and you will be able to guess anything.
It turns out I'm not nearly as good as I thought. I can nail a delay of 100,200,...,900ms exactly only about 40% of the time, and within +-100ms about 80% of the time.
If anyone else feels like trying, you can do "go get github.com/erinok/howlonghowlong". Hit space to see a flash, and then type 1-9 for how long you think the flash was.
It's surprisingly fun. (At least if you're incredibly weird like me.)
I find I'll have periods of concentration where I can just nail it, and then it'll leave me, and I'll be sloppy.
And thinking about it, in Trackmania it was less a perception of time that you noticed, but a sense of how smoothly and perfectly you had hit every turn. You could easily race the almost the exact same time multiple times in a row, and then feel it when you hit a turn more smoothly and shaved a few fractions of a second off your time. (Or similarly feel it when you screwed up and added a few seconds.)
Man, thinking about this is making me miss trackmania :)
But that misses the point of the Jobs story. Some people really do have sensitivity to things that the vast majority of others have trouble perceiving. Most people would have trouble perceiving a millimeter difference in spatial dimension by touch.
Having said all of that... the likelihood that the Project Manager in the original story... or even that the Project Manager in your workplace for that matter... is the maven that Steve Jobs was is remote in the extreme.
It is quite plausible for people who being to obsess over a certain aspect to become overly sensitive to it. In my case, a lifetime of playing high speed video games makes it possible to notice things that others miss when it comes to things like framerates and microstutter in computer graphics. I find it likely that Jobs and Page were able to pick up on millimeter & millisecond defects.