The short version:
If you've encountered the scenario above, make sure the user running PCW is in the designated Sharepoint Administration Group, not just added to the server with the Administrator Role.
The rest of the story:
I'm creating this note because I believe more than a few people out there have run into this scenario; lately, even Jason and I got burned by it.
The good news is that this particular issue turns out to be vague (and in one place, misleading) documentation. It starts with an invalid assumption, though a rational one: Being a Sharepoint Administrator and Being in the Sharepoint Administration Group are not the same thing. I hope I'm not the only one who thinks that's a little weird.
So, where it gets bad is if you stick to the shipped copy of the TFS Install Guide. It tells you that to run PCW, you need to be a Sharepoint Administrator, and then tells you the wrong way to do that. In truth, you need to be in the group that is marked as the Sharepoint Administration Group (from Sharepoint Central Administration - something you can't reach even as a Sharepoint Administrator, unless you're also in said Administration group).
The online Team Foundation documentation for managing permissions has the correction information, and you can find it here. Also, our documentation team is ("even as we speak!") updating the install guide, and with a little luck the online version should be updated this month (next month, with a little less luck).
It seems a little strange that a Sharepoint Central Admin has to designate a domain user or group to be 'the Sharepoint Admin Group', rather than simply creating a local group for that purpose. But, as with all things technical, there probably is (or at least, was) a good reason, if you dig down far enough. I'm hoping to ping someone on the Sharepoint team to find out the details.
[Update: If you still have problems with PCW, you should probably start here: Troubleshooting the New Team Project Wizard]
Slashdotters of the world, I have a new acronym for you: IANASPA (but I did stay at a Holiday Inn Express last night...)
I know you're a cannonball...