Hope this of some use everyone - just spent about 2 hours on call with Apple senior advisor...
Basically tried everything from removing libraries and files and reimporting - even went through the library with MusicBrains Picard and checked and repaired metadata.
Anyway got all of the already posted errors, timeouts, failed delivery of iTunes results etc. So I did screen sharing between two macs in the house, one with the physical library files and one with no library at all (signed out of iTunes account).
One of the other fixes which certainly improved the response on iTunes was to completely reset Safari (unchecking history and cookies) Website data for some reason. Also going into Network setting and making a new Network location.
So I had had Match running for a couple days on the Mac that I thought was playing up, which was failing on Step 1. While talking to the apple advisor signed into the other mac with no library and all of sudden about half my library was sitting there nicely matched and available to listen to.
Back over on the main mac with the physical files we were still getting the usual errors, the Advisor even checked with some internal iTunes store people and they were saying everything was normal, that iTunes was connecting and currently querying the store... "normally".
So I have a growing library of matched files on one mac, and on the machine with with te files every single file says "Waiting" as the iCloud status - so I'm geussing the connections between iTunes and iTunes servers are probably not stable, certainly dont return consistant results to users.
This was for a new library to iCloud - not a renewal of the Match service.
Remember you have 90 days support of the newest OSX operating system if you've installed it, or as a Match user you're likely entitled to support of iTunes Match as you've paid for it for the year.