I had a similar problem and after with uploading. My fix was related to me having moved my WP files to a new folder on my server. I then used a backed up version of the database. All else was running smooth except the MU function. I also tried the plugins and theme etc. Finally I found that in my settings tab there is a media page. Here I found ‘Store uploads in this folder’ and it shows the folder path it uses when attempting to upload your media files.
In my case it had a legacy server path from my old install. Seeing that this post refers to an upgrade it may pay to check that the path in this field is pointing to the right folder.
Of course I then checked the folder on the server that the previous path showed to and lo and behold there was a folder full of duplicate images that I was trying to upload.
Hope this helps.
