Deleted files can't be checked back out?

Hello all,

I recently deleted a bunch of files and checked the change into git, and then changed my mind and wanted the files back. I did a git-checkout <file> and got each file back individually. Then I did some work and did a git-push to upload to github. Then I did more work and tried to do a git push and it gave me an error that apparently meant I had to pull before I pushed. Anyway, I pulled, it redeleted the files and now when I do git-checkout <file> to get them back it says:

error: pathspec 'foo' did not match any file(s) known to git.

I'd really appreciate some help on this issue. I tried messing with qgit to look at it, but I didn't have much luck...

-fREW