Exactly the same problem here, brand new 2012 15r 2.3 8 256 mbp and an iphone4s. was furious that I accidentally deleted my entire itunes lib from my iphone as it slipped out of my hand just as the "match will erase everything" dialogue box appeared (I didn't even get to read it!) and as I grabbed onto the phone my finger hit the "ok" button. Could do with a "are you sure" dialogue or something, that was a royal PITA.
Anyway now I'm into day three of a service that I'm paying good money for that clearly has major errors, will not complete what ever this task is and appears designed to facilitate inconvenience rather than offer any demonstrable benefit!
For example, I looked on my iPhone, yes it appears that my music is there (after rebuilding my entire library of 7000+ tracks!) on the MacBook Pro. So I leave the house and go out for a coffee, get to the coffee shop and figure I'll listen to a few tracks whilst reading the paper, but no, they aren't on my phone anymore! they look like they are!! but no!!! this is a mere ghost of my music! almost mocking me with its 'slightly translucent' appearance.
WHAT THE HELL IS THE POINT OF THAT?!? how does that enrich my user experience?
I'm going to give a few more things a try (already tried turning off genius, logging in and out, standing on one leg, eating an apple, colourful language and various other internet borne suggestions), If I have no joy by lunchtime I'm heading into the nearest apple showroom and I'm inserting both my shiny new MBP and my i4s into the nearest available g'anus.