Now mine are gone, and searching for "Nokia Collection" doesn't show anything.
I hate to say it, but with the problems with the Titan's wifi problems, the Office Hub screwing up, and now this... I'm leaning toward an iPhone as replacement.
Had this issue with my 900 after an update. Didn't show up in Marketplace and nothing in searches.
So I found this on the Nokia forums, they told the user to open the Xbox Live app and wait until it finishes "updating" and you can actually see your avatar (swipe to right). Then you should see Nokia Collection on the 1at page of Marketplace.
This worked for me. After going letting Xbox Live load and looked at the avatar I went back to Marketplace and there it is right under AT&T Featured (for me) and above "apps". I'm on AT&T in the U.S..
Frankly they have such a nice selection of extras I was blown away.