"If What's New was THAT popular, they wouldn't have replaced it" - this is the crux of it. No business is going to make changes to their product if it is going to be unpoular with the majority of users. So this strongly suggests that they have made a purely commercial decision and. like it or not, live with it because the old, broken What's New" isn't coming back.
The recent "Browse" announcement underpins this as it appears they are bringing Tunigo to spotify which should show new releases, same as the stand-alone app does.
Instead of demanding the return of something which is gone forever, focus on posting and supporting ideas to make Discover better.
On an aside, Spotify really missed the ball on this change. Change theory suggests that they should have broken What's New to the point that users would have welcomed any replacement with open arms :)
Now that I'm better set up for running multiple versions, I'll have to give Tunigo another look. I've used the swarm.fm app, and that's pretty good in terms of new releases. I suspect What's New probably had a pretty limited demographic.
BTW, take a look at tag:new and tell me how many times Blurred Lines is listed. I know its popular, but....