Using git through the command line wasn't working, period. And yes, we know the difference between a tracked and untracked file guys, we aren't git retarded.
I eventually fired up the gui, and only through that were we able to properly remove the file. This has been an issue before, so I think it's a bug in Git-Scm's bash prompt.
EDIT:
Actually, I'm quite literally retarded. git commit <removed file>
http://ragefaces.s3.amazonaws.com/5041f6fdae7c704ffe000001/facepalm.png