Same problem here. I can't even verify my own number anymore here in Colombia because the text message with the verification code does not arrive to my own Colombian cellphone. The cell provider I use is movistar.
I'm thinking Movistar probably blocked skype somehow. The reason I think this is because that's the kind of thing cellphone carriers in general like to do to their clients: take away as much service as they can.
Same experience. I have tried multiplte times to send SMS to several different cell phone numbers in Colombia, all fail. I can call those same numbers using Skype, so the numbers are correct.