When I got my GNex I didn't have this problem - at least I didn't notice it. I had the box checked to auto-create a widget when I downloaded something from the market and I got annoyed with it taking up home screen space for every single thing so I unchecked that. Sometime after that, I started noticing that things I downloaded didn't show up in my home menu unless I restarted the phone. I just tried clearing the data/cache on the Market and downloaded something and still it doesn't create an icon for it. I imagine after I restart it'll be fine. I also tried re-enabling the auto-widget thing. Any ideas what is wrong and how I might fix it? It's marginally annoying having to restart just to get to my new apps. ETA - I also noticed that the icons from things I uninstall don't go away either until I restart.