I have the achievement already. HOA at 61. Still no quest.
After seeing this, I decided to give it a shot. It worked!
Killing Azshara (+achievement) finally made the Whispers of N’Zoth quest show up. Thank god.
Before killing Azshara, I tried going to different continents, logging in/out, re-equipping my Heart of Azeroth, walking in and out of the city on foot, doing some World Quests, abandoning a bunch of unrelated quests… no dice. The earth man stands there, mocking me.
My guess is if you’re far enough long that you should kill Azshara, then you have to. If you’ve barely touched the questline leading up to her, you don’t.
I was also able to take the followup quest in the Chamber (Spies to the Left & Right) from Kalecgos.
I’m not sure what all is relevant, so here’s my info–
Blood Elf Hunter, War Campaign: Complete, Heart of Azeroth: 63, Crucible of Flame: Rank 3, Faction: Horde, Gift of N’zoth: Yes, iLVL: 396
2 Likes
And still notta. 
Same bug, with an added twist. One of my characters can get it, but the other three I’ve checked on it doesn’t show up.
Each of them have varying degrees of a high heart level (55-63), exalted/not exalted CoA reputation, completion/non-completion of the war campaign, the death of Azshara, and the eyeball of N’Zoth, so I think we can rule all of those out.
Obviously 
I’d cleared the eternal palace before, had the circle of stars achievement, finished the war campaign… nothing.
I’m starting to wonder if the game has just randomly “forgotten” that some players have already killed Za’qul and Azshara, and we have to do it ONE MORE TIME after the patch in order to trigger anything.
I think that’s exactly what’s going on.