The basic error "could not complete iTunes Store request" is generally related to connectivity, anything from firewall settings through Date and Time Zone settings. I suspect the problem is not specific to Match, but that you don't use other iTunes functions that might also throw that error, so Match happens to be the place you run into it.
If you haven't already pursued it, try following this article:
http://support.apple.com/kb/TS1368
There have been several iTunes software updates since you originally reported the issue - have they had any effect? What about Mac/Windows/anti-virus updates?
I'm also curious as to how you're importing music into iTunes that "add to iCloud" would be a song-by-song option. As far as I know, Match wants everything that's in the library - if it doesn't automatically add while you're importing the music into iTunes, it periodically scans to see if there's something to be added, and if that fails, you have the option to manually Add (everything) to Match.
I don't see a track-by-track "add to iCloud" option, though I wouldn't, as everything I have is already in there, or it's automatically added when I import it. It doesn't mean it might not appear if you were offline (either had Match turned off, were not signed into your iTunes account, or didn't have an internet connection) when you imported into iTunes - but I also haven't come across that function in the support documents. All I see is:
I also don't see it listed in the Symbols used in iTunes article.
I get the impression you might be importing "offline" intentionally, in order to prevent the time-consuming upload of songs that you don't want to have in Match. Is that the case?