This has happened to me about 5-10 times now from going to Denim. I remember this problem happening Pre-Dev preview...It was addressed by a Verizon update and seemed to fix it but, it's back with Denim.
The only problem with this and it's pretty huge, is I look over my phone's tiles to see if I have new messages (email, texts, etc), I see no email I drop my phone in my pocket, it could be hours before I notice this problem. This is a MAJOR problem because the phone does not notify you that there is no internet. I could be missing some time sensitive emails and it could be more than just a little issue, it could possibly cause my job.
Yes,a reboot fixes it but, Needing to reboot is unacceptable...