See this
post where I have some times for how long it takes me to generate a 32x32x256 patch. Without the compression stuff it takes 0.04 ms so well above 60fps (with compression it's still around 60fps). Note that however, I'm only generating a 2D type terrain. BUT, for Minecraft style 3d terrain you should expect the same timing. I say this because I think Minecraft he only uses a single noise FBM "type"--i.e Perlin. Whereas in my setup I'm using a multifractal and perlin, plus other filters.
I don't know for sure though. You just have to mess around with it. I'm only at the beginning with my own terrain generation, I just have something up and running there is still a lot of work left to do.