I am recommending this from memory so bear with me. I am not at my Linux machine.
One thing I have always experienced with Voodoo3 cards is that they are extremely easy to overheat. We all know what happens with too much heat for too long .........
Anyway, did Fedora enable 3D acceleration during the install? You might ( and I mean might ) be having problems if you are tyring to push too high a bit rate for the Voodoo3 with Direct Rendering enabled.
I believe the command to check for Direct Rendering is as follows (make sure your root):
# glxinfo | grep rendering
It will tell you either yes or no with regards to Direct Rendering.
If you are, try switching the default bit depth of your video card driver to 16 in XF86Config. I enabled DRI with my Voodoo3 under Gentoo and you MUST use the 16 bit default depth for it to work reliably.
If you are not using DRI, maybe enabling it will help? It may not help but you will at least figure out how to get that Voodoo3 cranking out some serous FPS at some point. There is specific Voodoo3 information in the documentation at this site to get you going:
As mentioned previously, also try setting your monitor to 60 or 70Hz.
Hope this helps somehow.