I too experienced the issue "unfortunately, clock has stopped" after updating my phone to Lollipop. I called Verizon and they told me to do a factory restore, which I did. The issue still persisted.
I just called Verizon Wireless tech support back. The guy had seen this problem once before and found a fix for it. I haven't seen this fix posted on any website, but it worked immediately. Please let me know if this works for you
Go to Settings--Date and Time--Select Date Format, and then choose a date format. Once I picked 'regional' the clock worked without the error "unfortunately, clock has stopped"
I tried clearing cache and doing a factory reset, and it didn't work. You don't have to do this if this if selecting a date format works. Please comment and let me know if this helped you. I'm curious if this will work across the board. Maybe even for phones other than Samsung Galaxy S4. I'm stoked!