Hi, like many others I got Melodyne Essential 2 with Sonar a few years ago.  At the time there was a special deal where you could also upgrade to Melodyne Editor 2 for a small extra fee. I took advantage of this offer.  Unfortunately it now appears that this means I won't get the free update to Melodyne 4 that many other Cakewalk subscribers will now get.  Celemony only offer me a paid update when I follow the instructions.
 
Please can someone confirm if this is the case or whether other news will be announced?

As I understand it (and I'm in the same situation):
 
We can certainly get the free update to Melodyne 4 Essential, when it becomes available soon to Platinumites, by installing it from the CCC (which I have never done, as I had Editor installed already and hey, if it ain't broke...) - but we will not get a free upgrade to Editor 4 just because we bought an upgrade to Editor 2 previously. This seems reasonable to me. 
 
I have installed the demo of Studio 4 and am putting it through its paces. An upgrade to Studio from what we have is $125 at AudioDeluxe, which seems pretty cheap for the substantial improvements and new/increased functionality on offer - especially as Noel has dropped hints that further improvements to ARA integration, including tempo, are potentially/probably in the pipeline. I haven't decided yet - either I'll do that (likely), or I'll downgrade to Essential 4 when it drops. 
 
 

Are those sites like AudioDeluxe legit?

AudioDeluxe is legit. There are several legitimate resellers currently offering Melodyne upgrades.

There are a couple of options in this thread: http://forum.cakewalk.com/Upgrade-Melodyne-Editor-to-Editor-4-m3351789.aspx
 
Rocky

Melodyne 2 Editor to Melodyne 4 Studio for $125 is the almost-greatest no-brainers in the history of DAW history. 

Cakewalk has spoiled me. I legitimately felt entitled to a free upgrade from Celemony as its become something I expect. 

The upgrade to Essential 4 is free to any user of Melodyne Essential.

FYI: I did both renew SPlat and upgrade Melodyne from Audio Deluxe with no issue, and saved money.

I just got the email from Celemony and did the upgrade to 4. It was painless. I did need to uninstall the older version before I installed the new version.