Help HTC Tattoo network problem

[imaginois]

I got second hand HTC Tattoo the other day and I love it. The thing is I can connect to the mobile network for some reason. I am in Denmark currently and using Lebara mobile SIM card but I tried it with other network too. The phone doesn't select the network automatically and has problem connecting. On manual search I get all of the 4 mobile operators here in Denmark but I can't connect to neither of them. The message I get is "Your SIM card does not allow connection to this network"

I did hard reset on the phone but with no result

Please help