Did you check for updated video drivers? It sounds like you did all the other standard troubleshooting things for graphics issues. In the graphics options, I assume you tried changing the texture quality, disabling post processing, etc...