iPhone 3G software problem

I just got an iPhone 3G. Unfortunately the seller accidentally wiped the software on the phone while trying to factory reset it.

When I try connecting it to iTunes, it says it needs to be put in DFU mode. So I do that and iTunes recognizes DFU mode. Then I try to restore it and is says again that It needs to be put in DFU mode event though I already did. Is this a error with iTunes or something else?