To get it unblocked, you should have your PUCK number... if that doesn't work, you need to take your movil to a movistar office and they can do it for you. If your phone is blocked though because you tried the wrong PIN too many times, you may be out of luck. I had a phone that we couldn't get to work and took it to the store to get fixed... good thing too! They said if I had tried it just one more time, I'l be looking at getting a whole new phone chip!
So it depends on why your phone is blocked if they can fix it or not.
As for other movil companies, try amena or airtel. There are offices all over the place! Just ask around!