I know that my GPU is a little weaker than recommended GPU with 512 but even so I should be able to play at medium settings easily.
I wouldn't say that. I have the same graphics card, and it appears to me as if 256 MBs were a bit too few. It runs, okay, but it isn't as good as I had - personally - hoped.
First thing: Turn the shadows off. They consume imho far too much "calculation power".
