I was having the same trouble, and was advised from our Vendor to try that following:
1) Change the current time zone (EST presumably) to a different timezone. Reset the time zone (causes all registered phones to reset, which will happen fairly quickly)
2) Change that same timezone...