I'm still having this problem and it is extremely irritating. Somebody suggested unpinning the store tile, rebooting the phone and re-pinning it. The problem seems to stem from the fact that sometimes when the phone throws a fit and demands a soft reset, random background tasks get disabled and the store update is one of them! I only tried this alleged solution today so will have to wait until tomorrow morning to see whether or not it has worked.
EDIT: according to this
http://answers.microsoft.com/en-us/w...3915#LastReply
The potential fix is to do a soft reboot in between and also clear the IE history too.