Well, it's time for an update, and a partial solution. I wish I could edit my previous post, but I don't seem to have that option. So here goes another long post…
Although I still feel that this problem is something that Apple needs to resolve without user intervention, there is a way the user can deal with it themselves. As stated in another thread on this topic, the problem can generally be fixed by performing the following steps:
1) Remove the song(s) or album(s) in question from iTunes and iTunes Match (When deleting from iTunes, check the box to "Also delete this song from iCloud" -- but keep your files)
2) Force Update iTunes Match (Store Menu > Update iTunes Match)
3) Add the song(s) or album(s) back to iTunes
4) Force Update iTunes Match again (Store Menu > Update iTunes Match)
5) Try again to download the song(s) or album(s) from your other computer or mobile device -- in most cases it will now work without the error (an example of an exception is described below).
You may notice that certain songs now have a different iCloud status then they previously did. They may have been Matched, but now have been Uploaded, or possibly visa versa. Although a proper explanation still eludes me, I believe that somewhere therein lies the heart of the problem -- that the iCloud status for certain songs is no longer accurate, and that the system fails to correct itself as needed without user intervention.
So, the problem is easily fixable by the user, right? Well, sort of. Even assuming that each 'broken' album can be 'fixed' by spending time in iTunes removing it from and then re-adding it to iCloud -- that isn't the service that was paid for. Worse still, the process above isn't perfect, and here is an example of it failing using some of the same tracks previously mentioned in this thread ('Prolonging the Magic' album by 'Cake'):
Before performing the steps to correct the problem, tracks 1, 4, 6, 8, 10, 12, & 13 were all flagged as 'Matched' while tracks 2, 3, 5, 7, 9, & 11 were flagged as 'Uploaded'. After purging this album from iTunes/iCloud and then re-adding it, every track except #10 was re-uploaded, and flagged as such. Track #10, for whatever reason, was once again flagged as 'Matched'. Guess which track was now the *only* one that gave me the error when trying to download it on the iPhone? Yup, track #10. However, I then went through the steps to correct track #10 (yes, again, having just done this minutes before with the whole album) and *this time* it uploaded instead being flagged as Matched -- surprise, it now works from the iPhone!
On the other hand, performing those same steps to correct the problem on the self-titled album by Blind Melon was 100% successful on the first try, with no lingering problem tracks as there were in the previous example with Cake. In this case, before attempting the 'fix' on the Blind Melon album, I had every track except #7 flagged as Matched, with track #7 flagged as Uploaded. I was unable to download tracks 2, 5, 6, 8, & 10 which were all subject to the error in question. After performing the 'fix', tracks 1, 3, 4, 9, 11, & 12 were now flagged as Matched, and tracks 2, 5, 6, 7, 8, 10, and 13 were now flagged as Uploaded. The entire album downloaded just fine from my iPhone.
So, there is inconsistency in the matching process, and there are inconsistent results from performing this 'fix', but the potential does exist for the user to manually work around this error. Why is this so rotten? Well, for example, and besides being a giant time sink, if someone is away from their computer -- say for days or weeks on a trip -- they won't know there is a problem with an album or song until they encounter it, and will have no recourse for resolution until they return to their computer with iTunes and the original files. Not cool Apple, not cool.
It does not appear to be a problem with local corruption of the files, because the same exact files can be used as the source when 'fixing' the problem. Also, I have a very hard time believing that the problem would be actual data corruption on Apple's end, what with all their investments in state-of-the-art data centers for this explicit purpose. I suppose it could be an issue of 'network corruption' during transmission, but again that seems a lousy excuse when prior to this error cropping up those 'broken' files were perfectly downloadable.
What is actually going on? I do not know, but it sure it frustrating.