When I say it proceeds to start the installation I mean everything is the same way it's always been with updates. The phone restarts itself, there's a big, colored, moving, circle that represents the update installing. There's a bar right underneath it that shows me the progress of the installation, and about 1/4 into the installation it stops and there's a picture of a green Android robot with an Error message under it. Then the phone just restarts itself. And a day later I get another update notification.
Yes I have tried clearing the system catche. Somebody above suggested it earlier. Didn't work.