That's an odd error - I have no explanation for it.
Here's what worked for me.
Remember to turn off Find my iPhone, disable auto lock, turn off your passcode and put your iPhone into airplane mode.
Also if your device was previously jailbroken, you need to restore it rather than just update it. And, regardless, update it from your computer via USB rather than OTA.
1) (on the Mac) back up your iPhone in iTunes, then close the program
2) (on Windows) download Taig 2.3
3) (on Windows) If you're running an antivirus program like Sophos, disable it (re-enable when you're done)
4) Plug in your phone and make sure it's on the Parallels side
5) (on Windows) launch iTunes. When you've been prompted "Trust this computer?", on your phone say yes then close iTunes.
6) (on Windows) Launch Taig 2.3
7) Unselect the second checkbox (25PP or whatever it's called), then click the jailbreak button
8) Be patient - it may take a while
If the jailbreak fails, then go back to Mac iTunes and do a fresh restore of the iPhone. When I've had problems, I've found it helpful to restore as a new device, jailbreak that, and afterward restore from backup.
With a previously jailbroken iPad, the first 8.4 jailbreak attempt failed. I restored it as a new device, then tried to jailbreak it again - the second time worked.