Have you tried repairing and verifying permissions? Boot off your OS X disk and run Disk Utility. I remember having a similar problem, but I can't exactly remember what I did to fix it.
Use CCC to make a bootable back up. Boot from back up format your internal drive, clone data from external drive to internal. Boot from internal drive. Attempt Partition again.