For those confused by the MP3 conversion, or reasons why some work and some don't, I think this is the answer:
http://www.appsaffair.com/iphone-ipad-android-apps-news/this-item-is-not-eligibl e-for-icloud-%E2%80%93-what-0612201168100.html
Also, http://support.apple.com/kb/TS4124 is helpful.
In short, songs need to be encoded at 96Kbps or greater. Typically, older MP3s, for people trying to save space might have been encoded at less than this. I found a bunch of mine were.
As for converting them to MP3 again, iTunes will show a 'Convert to <format>' option where the format depends on your specific import settings defined in your "Import Settings" on the General tab of iTunes preferences. In terms of iCloud it really doesn't matter if you use MP3 or AAC, just as long as it's above 96 Kbps which all modern settings are.
So, right-click on any songs that have a lower bitrate, upload the new versions and trash the originals. Worked fine for me.
Now, as for those that were ineligible because they're protected, I found that I had a whole load duplicated, because iTunes had grabbed matched copies and left the original protected versions in place. Do a "Show Duplicates" and see if that's happened to you to. I trashed by original protected versions and kept the new purchased versions. The purchase date will show you the latest version. I found iTunes had already added them to my iCloud.
The only things I can't upload to my iCloud are the songs from my kids purchased with their own apple IDs, not mine. Those are few and far between and can't be helped.
As for "An error occured", I have no idea. I only have 4 out of over 6000 songs. A couple of those I bought from the iTunes store, so it not being able to match surprises me.
Hope that helped.