I have a problem with my iPhone 2G. I have a 3.1.3 on it.

Here is the problem:

I was in England and I had to unlock and jailbreak my iPhone to use O2. Everything worked fine, but later I moved to Finland and inserted Finnish "DNA" sim card. It worked for about two hours with no problems, but afterwards I tried to slide-unlock it and enter the passcode and it didn't work. I tried again a couple of times and it just showed me a red white on red text saying: "iPhone locked. Attach to iTunes."
I did so... but iTunes said: "iPhone is protected by the passcode and cannot be opened in iTunes. Please enter the passcode."

I tried jailbreaking/unlocking it again, but it didn't work. redsn0w did its work, I saw all the loading screen on the iPhone (although somehow it took less time, than people say it takes), and after it finished I rebooted my iPhone, but the problem remained.

Does anyone have any ideas?

I am not a very technical guy, but I thought if it is possible to simply empty the iPhone of its OS and reload it into it?
Kinda what you do when windows is acting up!

Thank you in advance!