TL;DR: Ship remaining Symbian phones with a single menu level of Apps; less than an entire page filled with icons. Move normally included free apps to OVI store. Let UX complexity be controlled by user, grow with user parallel with familiarity. Win for consumers and OVI traffic.
I've loaned our N8 to a few people in our office not connected to mobile development - just average consumers. They've been iPhone and Blackberry users. There's a lot of things they like about it, but one common complaint is it's too complicated.
I've been thinking about why I prefer Nokia's smartphones to Apple's, even when I agree that the menus are too deep and complicated on Symbian. I'd probably even call them intimidating for many new smartphone users. But why is iOS's icon sandbox preferred when it can result in pages and pages of icons?
One thing I like about the N8 is it does just about everything out of the box - Nokia smartphones are the swiss army knife of smartphones. There's a ton of apps to do everything, including a lot of stuff I'd never use. There's not a lot of motivation to visit OVI and see what else is available.
The iPhone, on the other hand, comes with a bare minimum of pre-installed apps, one of which is the app store to go get more apps. There's not even a full page of icons, and they're not nested. It's basically a UI sandbox for the user.
I think this is something Nokia could do with its few remaining Symbian devices to help the devices and promote OVI: put the majority of the included apps for the device on OVI for free, and deliver a UX that can grow with the user. Allow user to manage the complexity of the menus. I don't hear many iPhone power users complaining about icon avalanche. I think it's because THEY put them there, and their device's complexity grew with the user's familiarity.