Have you tried reinstalling Nokia Store by using the following process?
Symbian specialist until 31/01/2013 with interests in Maemo & MeeGo but an aversion to Windows!
I have an N8 with Belle.
Nokia support via phone after weeks of calls back and forth was not helpful. Everything they had me do did not work. This all started when upgrading from Anna to Belle. Trying to open store. I get the screen that says i need to update to 3.30.018. I click on update and then it seems like it is just about to start downloading, But then i get a message saying " Update error Required Update Failed" Options given are retry an cancel. Retry always repeats the same error. Cancel option closes app.
have tried to use the link that you provided http://lr.ovi.mobi/store/new-symbian-3 . On my PC and on my Nokia both in the nokia web app and opera mini. On all three locations i get a message " The service is not available for this terminal. " How can one get the sisx file to instal store.