My brother had this problem on his Elite. It was due to him having an incomplete download of an old demo on his hard drive. Deleting this data fixed the problem. He stopped the download but never resumed it and left the file on his disc.
I'm guessing the old demo keeps it's priority in the download queue regardless of whether its listed there or not and doesn't allow the patch files to be installed as there is still a file waiting to be installed ahead of the patch, thus, once you shut off the system, the patch gets deleted from the temporary cache.
Just go through your memory looking for the yellow exclamation point icon next to a piece of data and delete it. Hope that helps.