It depends on the game. Some low-action (not many objects moving) games are very playable at even 30 frames per second. The game that comes to mind is Need for Speed 3. Other games, like first person shooters, such as Quake 3, can have problems at 50 or 60 frames per second.
The key here is that these are <b>average</b> framerates which are very different from minimum framerates. Some games can average in the 70's, 80's and higher but occasionally drop into the single digits. This is very annoying.
So, as you say, higher is always better. The idea being that with a higher average the game will drop to unacceptable framerates far less often (or not at all). Realistically, I think most people consider 60 fps a comfortable level with die-hards shooting for rates in excess of the 100's.
Tom wrote an editorial article regarding the problems of using average framerates for benchmarking purposes. Sorry I don't have the link for it. It's interesting that everyone (including www.tomshardware.com) still uses average framerates for comparisons. I guess the developers are perfectly happy to show off their high framerates but would not be willing to advertise any weak points.
<P ID="edit"><FONT SIZE=-1><EM>Edited by phsstpok on 03/01/01 01:33 PM.</EM></FONT></P>
If you can keep your minimum framerate to above 40 fps then you'll be fine. Actually Quake 3 at 40 fps steady (which would never happen by the way) would be completely playable. The main reason why people want Q3 to run at 60+ fps is because that is the average frame rate. When you're running 60 fps average in Q3, your minimum is usually around 40 or so.