iTunes Match error 4010 when adding songs to iCloud
So what worked for me was to sign out of iTunes Store then sign back in.  This will disable iTunes Match. You then need to turn Match back on. It looks like it is starting completely from scratch (!) but it doesn't and instead adds all songs to iCloud that were missing.

I had 3 albums to add and I had to go through this process for each one.  I am assuming that something has changed or gone wrong on Apple's server side for it to start behaving this way when it previously worked fine.