Can't partition disk

I am trying to create a bootcamp partition on a Mid 2012 Macbook Pro.
However whenever I try to partition the disk I get an "Invalid partition" error.
After some disk utility mucking around I have discovered that it is the partitioning process itself that corrupts the disk!

From Disk Utility:
1. I verify the disk - No errors
2. I set a partition size, and click apply
3. I get the "Partition Failed with the error: The disk needs to be repaired..."
4. I go back and verify the disk, and hey presto I have a error "invalid directory item count"

hmm, my wife is thinking she needs to buy a PC at this point, any suggestions to get past this error?

Thanks