It could be your date and time settings, wrong date and time can cause problems like this. Check if you have the right date and time set in your phone. (Settings -> date+time) The best option is to set date and time automatically if you have a sim card.
I was facing the same issue because of i had been updated 8 to 8.1 through WiFi.. Sometimes some features are not working when you have update to it via WiFi. Just reinstall the Windows 8.1 from any service center.