It may just be that when a song is encoded at such a low bitrate (I mean 48kbps is REALLY, disgustingly low) it has already lost so much of the original waveform data that the matching algorithms can't recognize it with enough confidence to match it. You could be correct anyway in that maybe it's a different recording of the song, but I'm gathering that the unreliability of matching super-low bitrate songs is why Apple lists that as a restriction.
And Senseotech Do you still have the original files for those two "not eligible" tracks? If you do then test matching with those rather than the iTunes Match copies and see if you get a different result. Maybe you are right that the fact that they were downloaded from iTunes Match has nothing to do with it, but I wouldn't be surprised if it did. Maybe this is a new restriction that Apple is partially testing or something.
I'm also still interested in hearing from anyone who has tried to update an already matched library with new music (either from a CD you've ripped or an amazon mp3 album or whatever). Can you match just that one album without re-scanning your entire library? I'm sure a lot of people are interested in the answer to this.
Edit: TexasTexan I believe the two files that Senseotech is talking about were actually sourced from iTunes match--not only because he said they are 256kbps AAC files but if you go back to his other post he pasted a screenshot showing the file type as "Matched AAC Audio File". I believe that only shows for music downloaded via iTunes Match. That's why I thought it would be interesting to test again with the original music files to see if those are also classified as "not eligible".
And to whomever was wondering why iTunes Match is uploading cover art, even for matched songs. My guess is that it uploads the cover art if the original audio file has embedded artwork. iTunes itself doesn't embed artwork but other ripping/tagging apps do. And just as iTunes match preserves user-customized metadata, I'm guessing it also attempts to preserve user-embedded album art too. What I will be interested in seeing though is if it preserves the original resolution of the artwork or if it downrezzes it to something crappy. Speaking for myself, I always embed 500x500 artwork in all my audio files. So if iTunes Match will preserve that for me then I'll be a happy camper.