I had submitted a change-list containing some new files and then for some reason had to back-out.
Now I am trying to submit a new change-list that adds the same file back.
The problem is that when I backed-out, it deleted those files from HEAD revision and now when I am trying to submit my change-list it says 'Out of date files must be resolved or reverted'
I tried googling the solution but could not find anything relevant, can somebody please guide me right direction?
You just need to back out the first back-out. (When you say you backed out the addition, you mean you also submitted it, right?)
Locate the changelist that you submitted, e.g. via P4V's Submitted tab, right-click and choose Back Out....
It's best if the files you're trying to resurrect (re-add) don't already exist on your filesystem, otherwise Perforce will refuse to overwrite them. (Which may be what the error message is telling you; I'm not sure.)