Can you describe the issues on the 800? I'm not familiar with them.
I'm using Ultimate Ears Triple-Fi 10's. Tried both my Focus and the Lumia 900 and my old Zune HD. I'd rate them from lowest to highest, Focus, L900 and Zune HD, however the L900 is closer to the Focus than the Zune (which had very good AQ). There wasn't much discernable difference between the Focus and L900, L900 seemed to have a milder high end and fuller mid-range, although that could simply be software EQ differences and the next person may put the two in opposite order. If I were to score the Zune HD as a 9 on quality, I'd put the L900 and Focus in the 6-7 range. That's definitiely not so say they're bad. It's by far good enough for me to almost never carry around the Zune anymore. It's just not "audiophile" quality and honestly if that matters to you more than anything else, I'm not entirely sure any phone is going to be good enough.
Also, since someone said there are no audiophiles are here (don't assume, snob), I figure I'd go a step further and test on my regular stereo for you - Emotiva XPA-5 / Onkyo TX-SR786 as a pre, and Martin Logan Vantages. I cringe everytime I play lossy music through these things. Results are pretty much the same as before, however the difference in quality between the two phones and the Zune was much more noticable.
Honestly as long as you take the limitations into account (it's a cell phone, not an audiophile grade device), I'd be surprised if you were unhappy with the L900.