Did you make sure to include the collection name in the url passed to the git-tf command? My company had problems exactly like you describe and that was the fix.
This: git-tf clone http://<server>:<port>/tfs/<collection name> $/<project name>
Not this: git-tf clone http://<server>:<port>/tfs/ $/<project name>
Hope this helps.