`git-p4 clone` fails "new tip ... does not contain ..."

I've had a similar problem and can usually be traced to the casing in paths, branch names, etc. Not sure about P4 but ensure that you don't have a Master branch - it should be master. Follow the same regiment across the board. Also, avoid directory and file names with spaces in them. A lot of git-centric tooling does not like that. Gitolite is one example. It will not allow a repository that has a space in it.

Similar to the accepted answer, I had this same problem when trying to sync to a git branch in the form:

git p4 sync --branch=feature/f1 //depot/path/to/code

The / in the branch name appeared to cause the same cryptic fast-import failed warning. Unfortunately git-p4 doesn't seem to support standard git-flow branch names.

Changing to a branch like this worked:

git p4 sync --branch=f1 //depot/path/to/code

I also encountered the "new tip x does not contain y" error running fast-import.

In my case, this was caused by an unrelated preexisting commit in the master branch of the repo I was attempting to import into. I had initialized the repo with the GitHub client which added an initial commit (to add a .gitignore file). The fast-import tool presumably could not reconcile the imported commits with the current state of the branch since the GitHub tool's commit had no relationship with the commits being imported.

The solution for me was to instead initialize an empty repo with "git init" and then run fast-import.