phew, august, well this is a bit late, but i'm getting the same error with a complete kickass machine and video card. i'm not too tech savvy, but i'm fairly sure it's a simple compatibility issue with god knows what. i've tried different compatbilities, 256 colors, all resolutions, nothing.
however with a surprisingly little bit of searching with google, you can see many others with recent computers have had the same problem, a very easy solution seems to be to download a sort of launcher like the one before you start red faction, called pure faction. I believe it's multiplayer based, but it'll bring you to the main menu, and I guess downloads to your red faction their multiplayer maps and optional map editor.
but it seems to fix nearly all of the problem, sure fixed it for me, as far as I know, it is only for the first red faction.
it's located at: http://www.purefaction.org/
hehe, you're welcome ^^
seems to be virus free btw, so *shrug*