I don't readily have a solution as it seems Marketplace has been having problems lately. All I could suggest is you look through this link and try reinstalling. I know you said you did that already but that's all I have right now.
Anyway in this link there is information to support pages -
Download the Games for Windows Client | PC Games Client - Xbox.com although I do note the Games For Windows link appears to be dead so
To be honest I get the feeling Microsoft is killing off, or is going to kill off, the PC side if Market Place. Note the
xbox.com in the link, and on the page.
Sorry.