The bad news: With automatic tracing algorithms alone, you won't be able to get a clean result. There will always be noise.
The good news: If you're willing to invest just a bit of effort in manual cleanup, you can get a very decent vectorized reconstruction. This is what I was able to get in roughly 5 minutes:

(Click on the image for a high-res version or jump straight to the SVG at the bottom.)
Here's what I did:
- Run "Trace Bitmap" on the original twice, once using "Brightness Cutoff" at 0.45 and once using "Multiple scans: Colors" with 6 scans.

In the "Mode" tab, make sure the fields "Smooth", "Stack scans" and "Remove background" are all unchecked. These were my "Options" for both traces:

Put the result of the "Brightness Cutoff" on the side. It is actually really good and gives you all the blacks (as pointed out by Juancho). So all that's missing is the colored areas.
Separate the 6 color layers, delete the ones that contain just noise, clean the remaining layers until you're left with the missing big colored patches:

Hint: To delete the noise, enter "Node selection mode" (F2), select a bunch of noisy nodes by dragging a box around them and delete them with Ctrl+Del
.
- Align the patches. If some patches seem to have been "thinned out" slightly during tracing, you can "fatten them up" again with "Path" > "Outset" (or
Ctrl+)
). Finally, group the result.
And there you have your reconstructed SVG:

Right-click and "Save image as..." on the above image or click here to download the standalone SVG file.