Problems connecting mobile network

Hi there,
Once I´ve done a factory reset to my Galaxy S, it can´t find a mobile network anymore.
I already read lots of posts from persons having the same problem that I, and already tried following:
1. Factory reseting again
2. Turn Power off and on
3. Hard reseting
4. Selecting APN manually
5. Turn Flight Mode on and off

Nothing seems to fix the problem. And when I choose Select APN automatically, it finds it, but I get the message "Your SIM card does not allow a connection with this network."

When I called Samsung, they told me it could be a hardware problem, but I found it strange, since it happened only after I reset it. Should be more a software problem, don´t you think?

Did someone here get the same problem and was abble to fix it?

Yes, I tried to select it automatically and manually. When I ask him to find the operator for me, it, sometimes find it, but when I select it, I get the message "Your SIM card does not allow a connection with this network." But my SIM Card works fine in other devices.
I also tried to put another SIM Card from another operator in the phone and it simply cannot find the right operator. It keeps showing me the old one. Even when I reset the phone again...

Pls. dial *#7465625#
What can you see?