I had the same issue and was able to resolve it by doing a hard reset on the invoke. You need to press the small button on the left of the microphone button using a small pin, this will do a factory reset of the invoke, after it's done you can pair it with the Cortana app on the phone again and connect it to wifi and download the update. I'm using Cortana on an iPhone.
Hope this helps. This worked for me
Ah, good. I was having trouble getting them to set up again. I have four Cortana/Invoke speakers in different parts of the house, and two of them were basically semi-bricked already. Doing a factory reset like you suggested let me get them working again.
You know, there is a USB port in the Invoke for upgrades. It would have been nice to have had a simple Windows program that would do the de-cerebration directly, rather than counting on it happening via the network at some indeterminate time. Sigh.