One of my colleagues couldn’t create a new Team Project although he was assigned the Project Collection Administrator role.
After some investigation we found that the problem was caused by SharePoint. Just assigning the Project Collection Administrator role isn’t enough. The user must have site collection administrator rights on the collection http://yourtfsserver/sites/DefaultCollection/ level.