The post from neopirus actually led me to the solution for this issue - in my case at least. There seems to be a problem with FileVault encryption, where the process pauses for no reason and then gets stuck at that point. This then seems to block any attempt to format the disk, for whatever reason, whether it be the installation of Bootcamp / Windows, or even simply creating a new partition through Disk Utility. In all other aspects, the disk is fine, and the various verify/repair procedures suggested neither report nor fix any problems.
At the time of writing this post, there is no fix for the encryption problem, although certain users have had success with various suggestions (see FileVault stuck on "Encryption Paused"). I needed to erase all the data on my drive and reinstall OS X, making sure I turned file encryption OFF. Bootcamp then worked perfectly - no partition errors, no problems at all.
I hope that helps someone, and maybe saves them the five hours I wasted trying to overcome this problem.