After a lot of frustration I finally got it to work with the suggestions here.
This solution may work for people who have their music on an external drive.
ONLY FOR PEOPLE LIKE ME WHO HAVE TRIED EVERYTHING ELSE. THIS TAKES FOREVER
My take on this, is that is is a problem on the side of Apple’s server, so nothing you do with your own library will help.
These are the steps I took.
1. Restart iTunes
2. Run "Update Genius" to get all the songs statuses straight
3. Run "Update iTunes Match" until it gets stuck.
Now all the song that still need to be uploaded are on status "waiting".
Because the songs have this status, the option to right click and hit "add to iCloud" is not there.
4. I force-removed the external disk and waited for the "iTunes Match update" to finish (it finishes because it can't find the songs anymore).
I used the Terminal to remove the disk with the line:
diskutil unmountDisk force [disk location]
If you have your songs on your startup disk, maybe temporarily changing the folder where the songs live could create the same effect. I haven't checked though.
Now the songs that have to be uploaded are marked as "error" (the cloud with the !-mark)
5. Make a smart playlist with the following filter:
- iCloud status is error.
6. Quit iTunes
7. Reconnect the disk/re-rename the folder
8. Open iTunes and play a song to make sure the connection works, preferably something by Squarepusher
9. Create a "normal playlist",
10. Drag all the items from the smart playlist into it.
11. Select a couple songs, right click and "add to iCloud"
12. Wait for it to finish or stop the process if it gets stuck
For me, a batch for 25 songs per seemed to give me the least problems.
13. Rince and repeat
It took me a full saturday and sunday to complete this process.
It’s damaged my liking to Apple quite a bit. I hope they fix the issues soon, I wouldn't want too much people having to go truth all this.
If it's all in the cloud, the service seem to work fine.
Hope this helps!