At viipottaja's request here are some of the reasons:
Difficulty in making it available in multiple markets. There are different legal requirements for each market with this sort of thing. We already see this with a lot of Noki's Ovi services. There's obvious benefits to have something simpler (more controlled) that you can have available in all markets (Download! as it is now). It's not just legal requirements either - think about localisation in terms of language, terms and conditions, currencies, payment processing etc etc. Creating a app store platform that is flexible enough to deal with this sort of thing is hard...
Variances within applications - there's multiple way developers collect money - be it via OpenBit's LM or similar, via aggregators, via operators... Chances are for a store to work you'll have to create a standard way of doing payments. Developers will have to support that. Trials? Subscriptions? How does this play against what's in the marketplace already? [N.B. Only freeware in Android marketplace at launch]
You have to partner with people and there is a cost to that. It's quite easy to this and be transparent about it and of low cost when you're delivering to a limied market. BUT it will go up the more devices you have on the market and will go up as your ecosystem get more complex. Nokia's mobile ecosystem is enormous... Yes this is a bit of cop out, but it's also true.
Multiple devices - it harder to do with multiple devices - more testing (yes most things will just work, but not always... This is an area where legacy and wide platform reach hurts.
Operators - Nokia still sells most of its phone trough operators / carriers. They are the main customers and what they want goes. They're unlikely to approve of app stores on lower end phones, especially on devices where they have their own download type offering (even if it is just cruddy Java stuff). Nokia will therefore be more inclined to spend time and money on the requirements they do want (e.g. look at the fuss Ovi has and is still causing). Some operators will even remove Download (and that was designed to keep them happy by including pSMS revenue)! I personally suspect this is the biggest single reason Nokia hasn't done much in this area until a year ago. Of course once the success of the app store became apparent clearly a response was needed... but it will take time, and the operator issue is still the elephant in the room.
Ironically it's actually easier for new entrants focused on the high end (Android, iPhone) as there's no pre-existing framework i.e. its not something new, its part of the package...
In the Symban World apps stores have kind of fallen between the responsibility of Symbian Ltd., Manufacturers (like Nokia), and operators. All would probably liek to do them, but it seems to me that there hasn't been the will.
That said it should be possible, but its not a simple case of taking a list of applications and making them available in a client.
Please note this isn't intended to be complete and its off the cuff rather than carefully written (and there's probably stuff missing).