I don't know how much difference it makes, just noticed that "video editing" is the most common justification for buying a quad core in spec me threads on here. This software tends to be competently multithreaded so quad cores really do perform twice as well as dual cores.
When you say cheap as possible, what sort of bracket are you looking at? How's he feel about second hand parts?
I put an Intel motherboard / e8400 / 4gb corsair together for my girlfriend's mum a little while back, came to about 400 in total but it was new components with an antec mini P180. Astonishing how fast a 3ghz dual core is.