I'm also unable to login on Skype for Android.
Phone: HTC One S
Provider: T Mobile
Error message: You cannot be signed in at this time. Please check your mobile network settings and try again.
I don't see anything immediately wrong with my network settings. I've tried uninstalling and reinstalling the app - no difference.
I can sign into Skype for Windows on my PC no problem.