A new GPU would be a good move, something like an R9 280X would be ideal. (If you want to stick with nvidia then I wouldn't advise getting anything with less that 3Gb of Vram)
What OS are you using? Upgrading from windows 7 to windows 8 / 8.1 also give a good performance upgrade for systems that can make use of direct x 11.1
A core i5, 8gb ram and a 580. I think if he just used high settings instead of ultra (which he is obviously using for it to be "slow") he would be fine.