That could be caused by your network, or the software on your iPhone. The latest version for the iPhone 4s is 8.3.
Maybe the problem doesn't exist any more as soon as you have a better internet connection.
Here are a few more ideas. Try these before removing iCloud and setting it up again:
Make sure time and date are right on your iPhone.
Turn off Contacts and Calendars in Settings - iCloud, and enable them again.
In Settings - Mail, Contacts, Calendars, make sure you use iCloud as your default account. iCloud should also be set up as your default calendar.