A bit late to respond, but... I did Skype lessons on echineselearning.com for a year and a half. The service is located in Xi'an. I went from not being able to count to ten in Mandarin, to being able to discuss my teacher's social life.
PLUSES: 1) Lessons can be as strict grammar-oriented or semi-casual conversation-oriented as you choose; 2) You work with a single tutor, who really gets to know your language-learning issues; 3) It's much, much cheaper than most in-classroom language classes, and you obviously do it in the place you feel most comfortable; 4) The textbook, though unknown outside China, has flashcard sets that can be used in Pleco and AnkiDroid; 5) Specifically about echineselearning: I shopped around first and found numerous "schools" which had the appearance of online dating services, in which you could select pretty female teachers on the "sweetness" of their voice, whereas only a few services, echineselearning among them, claim that all their teachers are university graduates in appropriate fields and certified to teach. Mine certainly was: a degree in teaching Chinese as a foreign language, and some sort of official certification. She was whip-smart and spoke excellent English, which she only used when necessary.
MINUSES: 1) The textbook, while quite good, seems to include outdated terminology and phrases, and is outrageously expensive to buy outside of mainland China; 2) The downside of your dirt-cheap tuition is that your teacher is obscenely underpaid (I found out much later), something you have to be willing to deal with, and is likely to be a fresh graduate with limited experience; 3) Internet can be unpredictable. These teachers don't go to the office; they mostly work from home on their own laptops, and it can be the luck of the draw whether their building has reliable Internet; my teacher's original apartment had often-dodgy connections, but thankfully she moved, then things were fine. 4) These teachers are predominantly young women who are university-educated, and some may consider themselves in the market for a rich blue-eyed knight in shining armor, which in my case, seeing this woman 5 days a week for a year and a half, led to a bit of discomfort.