I face this problem quite frequently while installing Bootcamp on clients' computers, and we finally figured out the solution.
This error occurs when there are damaged files on the partition, preventing it from being able to resize. Boot off of your OS X installation disk, and repair the hard drive. This will fix any bad sectors, allowing you to successfully resize the partition and install boot camp. Note that this is different from repairing permissions, which you say you've already done.
Boot off of your OS X disk. On the "Install Mac OS X" screen, click on the "Utilities" menu at the top of the screen, and choose disk utility.

Select your Machintosh HD, then click on "Repair Disk". The disk verification utility will run and correct any errors it finds.

When it is complete, quit the Disk Utility, then quit the Mac OS X installer. Reboot to the startup disk, then try the bootcamp installation again. It should now successfully repartition your hard drive.

If this doesn't work, try booting into single-user mode and using fsck. Press Command+s as the machine starts up. This will boot into single-user mode, which is just a command prompt logged in as root. Use fsck to repair the hard drive. This is essentially what the disk utility does, but sometimes works when the disk repair does not. Use the command fsck -fy to repair the disk.