A solution at last.
Try disabling UAC and then installing MSN Premium. I did that and it now
will install. At first it didn't seem like it was going to work but now it
does.
You will still get a compatibility warning (which you can turn off) but it
is working for me now with RC1