Movistar were okish when my problems were limited to spending a fortune on calling other mobiles. As mentioned before they regularly have double and triple your credit days which makes calling cheaper.
I now use an iphone with movistar. Coverage and download speeds are miserable. Their 3G service is horrible, and I can't ever rely on it when I'm out and about. I'd change, but the hassle involved looks unappealing, and I've had the same number for years. Can't commend on Personal and Claro, most of the people I know are on Movistar and with standard packages they offer free calls between movistar phones. Might be worth finding out which network your main contacts are with and going with that.