I can't believe I'm paying for such a crap experience! The turning iTunes match on/off thing must have been a fluke. I am now down to under 2,000 tracks, but I'm losing patience. I can basically upload about 150 tracks per day. I tried deleting all of the error and ineligible tracks in my library, but that didn't really change anything.
This weekend I'm going to try re-encoding some of the remaining tracks in the hopes that they will be recognized by the matching algorithm. I will also experiment with resetting my router to see if there is some issue there. I didn't realize I was going to be a Beta tester for this service! A bit of a warning would have been nice Apple!