Unfortunately, I had the same issue when I first signed up. It took me 5 stops and starts before it got everything in. The jury is still out on this, as it won't get much better after this dazzling entry into the cloud. Now that I use it, I listen to about the first two songs of an album through my iPhone 4, max, and then the track stops and starts and runs the downloading circle. Very frustrating.
I found a solution in case your MATCH is still buggy...
JUST BOOT YOUR MAC HOLDING THE SHIFT KEY (until you see a progress bar).
Then in itunes disable and re-enable iTunes Match.
It should rescan all your library and eventually works.
At the end just reboot your Mac normally.
Best regards from Paris.