error: The following untracked working tree files would be overwritten by checkout

This could also happen due to a case change on the filename. I had the same problem and this is what solved it for me.

git config core.ignorecase true

True for Mac or PC.

Alternative solutions at: The following untracked working tree files would be overwritten by checkout

Without a complete picture of the repo, what follows is more of a guess than anything else, but it might explain the situation. Let's say your history looks as follows:

A -- C [origin/master]
  \ 
   B [HEAD, master]

You write:

This file has been coming up constantly and when I remove it from file system, git will say I removed this file, while in the other messages, it says it is untracked.

I'm guessing you may have run

git rm --cached <file-in-question>

and committed that deletion in commit B; therefore, the file is no longer tracked in your local repo and but it's still present in your working tree.

In the meantime, the upstream branch received commit C from one of your collaborators, in which <file-in-question> was not removed from version control. What you're attempting to effect with

git pull --rebase

is something like this:

 A -- C [origin/master]
       \ 
        B' [HEAD, master]

However, as the message says,

The [...] untracked working tree [file] would be overwritten by checkout

Indeed, rewinding commit C (in order to replay B on top of it) would result in the revision of <file-in-question> (from commit C) to be checked out in your working tree, in which an untracked file of the same name already exists. The contents of that untracked file may be valuable; you may not want that file to be overwritten by a another version of it. Therefore, Git stops in its track and tells you what's wrong.

Edit: Here is a baby example that reproduces the situation...

cd ~/Desktop
mkdir test
cd test
git init
touch README.md
git add README.md
git commit -m "add README"

# simulate a remote branch moving ahead by one commit
# (that doesn't remove the README)
git checkout -b origin_master
printf "This is a README.\n" > README.md
git add README.md
git commit -m "add description in README"

# remove the README and create a new commit on master
git checkout master
git rm --cached README.md
git commit -m "remove README"

# simulate an attempt to rebase master to its "upstream" branch, origin_master
git rebase --onto origin_master master

That last command spews out the following:

First, rewinding head to replay your work on top of it...
error: The following untracked working tree files would be overwritten by checkout:
    README.md
Please move or remove them before you can switch branches.
Aborting
could not detach HEAD

I suggest you run

git fetch
git log --stat origin/master..master -- <file-in-question>

to check whether something like that happened.

Remove all untracked files (carefull):

git clean  -d  -fx ""