It's quite an annoying experience. Had to do it a few times recently...
You can either do a quick restore which will keep all your files, or a full restore which will delete them. You'll need to download all updates (currently around 80 of them!) then reset. Then search again and there will be more updates that it didn't find the first time!
No idea why it does this but after you've done that 2-3 times you'll finally be able to see Windows 8.1 in the Store.