Since GSM protocol is at ~6 Kbp/s if I remember well, and it has a good enough voice quality, I can only imagine what Skype can do with 36 Kbp/s.

DSL 384 costs about 25-40 EUROS/month here.