Having bagged the 5800 on the morning, and gotten the goody bag to go with it, I can say I'm both very happy with Nokia and pleasantly impressed with 5800 which will now become one of my two (in use) handsets until the N97 is released.
Nokia did a really good job at the Regent Street store, and it's fair to say that it's the first time I've been there when there was a buzz around. I was very lucky in that I didn't really have to queue but still managed to get all the goodies.
I normally go through at least three handsets each year (with my last three being E90, iPhone 3G and Android Dev Phone) so feel I can have a reasonable opinion on the 5800.
It's a very good device, and I agree with the store staff member who told me that this was in his opinion the best Nokia handset yet (which is available to buy). Having really enjoyed using the N95, I can say that this is a good step up.
There are some usability 'hmmms' and the lack of an App Store is a big issue for me, where is the Twitter client? The fact is though that the 5800 doesn't need the App Store as much as say the gPhones / iPhones do, since it is a much more rounded phone.
Having had the iPhone 3G as my main device for a few months, it's great to be able to take half decent snaps and pretty good videos (in daylight). It's also great to listen to music and watch the BBC iPlayer with the phone on it's mini stand.
Other essentials (for me) are also delivered such as being able to run more than one app at a time; decent response on the Maps application (which works very well and doesn't rely on net access); being able to use the phone as a 3G modem by my laptop; and decent syncing with Outlook (left out of Android).
The key thing for me is that the phone is nicely responsive and works very well for the essentials such as calling, SMS'ing, listening to music, browsing and navigating.
Where things are weak are where Nokia have tried to reduce the learning curve for existing Nokia users at the expense of making things more intuitive for touch screens. The UI still has to be learnt so they would have been better off being a little bolder.
My key gripes, and ones which I hope Nokia will overcome fast are: Confusing OVI client, and no recognition of the 5800 on Ovi.com at all, you simply can't register the phone (i.e. 5800) on it. The desktop bundle is huge but totally non-intuitive. Why does Nokia Music insist on re-encoding all my MP3s? You're much better off simply using Windows Media Player to sync music. No NGage. No App Store (Downloads doesn't count as it's so poor).
The other thing to keep in mind is that there is not a lot of 3rd party software available for this handset (practically none) when compared to the previous generation, or the iPhone.
It's clear that the first true 5th Gen device from Nokia will be the N97 and this is something of a trial device. For the price though you get a great phone, and this device will replace dozens of existing low to mid range Nokia devices, especially as it will be free on many contracts.