As in the title, how tough is it to eliminate the background noises of this video?
To remove the noise you need a software capable of FFT (Fourier) based analysis. This may sound complex, but it's a simple operation of marking an area where only the noise is, then run the filter which will try to remove the noise marked.
Be aware though, this has some squicky (literally) side-effects making parts of the audio sound hollow and with small "squicks" here and there.
Room reflection / reverb require a different approach. It cannot be removed itself, but you can reduce it by chaining gate, limiter and compressor. The settings for each must be adjusted based on the sound. Start with the gate to find threshold and attack. To little attack will make it sound very unnatural so be gentle on this one. Use the limiter to amplify the audio and then the compressor to "compress" the sound down again.
I don't have a setup where I am to try different settings and so forth, so this last part is just from top of my head.
Recommendations for noise removal:
As omphteliba recommended, Adobe Soundbooth. But in addition, this little guy is low-budget but can do amazing stuff:
If you have Adobe Soundbooth you can use the clean-up feature. You select a part of the video that only has the noise and Soundbooth tries to filter out the noise when the two people speak. Your mileage may vary.