Parallels has finally posted a fix:
http://kb.parallels.com/entry/30/516/
However, it doesn't tell you how to get your Parallels VM to boot from the Windows CD in the first place. The trick is to start the VM, then go to edit/Virtual Machine, and in there you'll find an option to change the Boot order to CD first.
In my case, this only partially fixed the problem, perhaps because I'd previously botched things by following other advice on the internet. The solution for me was to completely deinstall parallels (using the _installer_, weirdly), then reinstalling it. Be warned that this might then need you to reactivate your windows installation.