See what happens when you buy a phone from an operator?
Do yourself a favor and buy unlocked. If you’re in Europe than go for Expansys, if you’re in America then check out Mobile Planet.
I’m not being paid to plug those two sites, they’re just highly known among the importing crowd.
If you want to know where I got my Nokia E61 it was a little company called Saber Point.