If iTunes can not find the files on the HDD it highly unlikely iTunes Match caused the problem. The files were probably already missing for whatever reason.
However the best course of action is to disable iTM and restore your iTunes folder from the backup immediately prior to activating iTM (which you imply you have). Then you should be able to determine whether the files were missing then, or not, and take steps to restore those files.
The details are important - you'll have to spill them all, at lest the relevant ones, because this isn't a game of 20 questions. But I'll bite anway -
Are you using iTunes on a Mac or a PC?
iTunes 10 or iTunes 11?
Did you add the files before turning on match, or after? or both (if both, which batch were the missing files in)?
After you turned on match, did you delete your files thinking you no longer need them?
Did you have iTunes set to copy and organize your files, or had you taken the manual route? (the settings are in iTunes Preferences, under "Advanced")
Have you recently renamed your hard drive, or some of your folders, or moved a folder that had music in it?
Does the location of your music library in iTunes Preferences --> Advanced match the actual location of your music?
Right-click one of the missing songs, and choose "Get Info" - does the location of the file match where it really is on the hard drive? If not, what's different?
Do you care about things like play counts, last played dates etc.? If not, you can just re-add all your music files (basically, start over fresh)