I had this error message even after rebooting my phone. It turns out I had too many of my own apps on the phone, three is too many apparently! After deleting a couple everything was fine.