The Startup disk cannot be partitioned or restored to a single partition

Were you able to create a Boot Camp partition originally? When you tried to remove it did you use Boot Camp Assistant to remove the partition?

The error you received usually occurs when you try to create a Boot Camp partition on a drive that is either too fragmented for the partition size selected or the drive is improperly partitioned already. From what you've written it sounds as though you never successfully created a Boot Camp partition.

Until I know what your actual situation is I cannot properly advise you on what next to do.

Open Disk Utility in the Utilities folder. Select the hard drive entry (mfgr.'s ID and drive size) which is the top entry, then click on the Partition tab in the DU main window. You will see a visual rectangle depicting the drive's partitions. You "normal" hard drive has a single partition that takes up the entire rectangle. If there's a second partition, the rectangle is divided into two parts. The topmost part is the OS X partition. The lower part would be the Boot Camp partition if it still exists. If you see this second partition then click inside the lower part. It will appear surrounded by a dark blue rectangle. Now, click on the [-] Delete button to remove this partition. Use the mouse to grab the sizing gadget in the remaining rectangle's lower right corner. Pull the gadget to the bottom of the rectangular area as far as it will go. Now click on the Partition button and wait for the process to complete. When it does you should now be back to your drive's original state and size.

And what happens if you open Boot Camp Assistant and try to remove the partition?

Then apparently something was damaged either when you originally partitioned the drive or when installing Windows.

I'd suggest doing as instructed: backup the OS X partition to another drive then re-partition the drive back to a single partition. Restore the backup.

I suggest you clone the OS X partition to another drive using the Restore option of Disk Utility:

Clone using Restore Option of Disk Utility

1. Open Disk Utility from the Utilities folder.
2. Select the destination volume from the left side list.
3. Click on the Erase tab in the DU main window. Set the format type to Mac OS Extended (journaled, if available) and click on the Erase button. This step can be skipped if the destination has already been freshly erased.
4. Click on the Restore tab in the DU main window.
5. Select the destination volume from the left side list and drag it to the Destination entry field.
6. Select the source volume from the left side list and drag it to the Source entry field.
7. Double-check you got it right, then click on the Restore button.

Destination means the external backup drive.
Source means the internal OS X volume.

Then boot from the external drive by restarting the computer and after the chime press and hold down the OPTION button until the boot manager screen appears. Select the icon of the external drive then click on the downward pointing arrow. After the computer starts up from the external drive use Disk Utility to re-partition the internal drive, then restore the clone per the above instructions only now Destination refers to the internal drive and Source refers to the external drive.

I had the same issue. Defragementing will fix your issue. Sasfly, osx won't do it no the level you need it alone, you'll need an app like idefrag to do it. when it happened to me, i was told it has something to do with the free space on the os x volujme being too fragmented to accomodate the addition of the bootcamp partion.

I defragged overnight with idefrag and it worked just fine.