Delete the partition and recreate it very slightly smaller in size, then format it.
Of course it may depend on how you have the disk partitioned ...... are you trying to exceed the number of partitions or mix up types of partitions?
More info would be required about the partitioning .....
JohnBoy: I had 4 partitions as:
1 x NTFS Win7 install;
1 x NTFS WinXp install;
1 x NTFS DATA DISK
1 x EXT3 PCLinuxOS 2009.2 KDE 3.5x install
I wanted to give KDE4 a proper tryout (e.g. NOT in a VirtualBox environment) and wanted to remove any lingering detritus so I thought why not simply reformat the Linux partition and have a fresh install of PCLinuxOS and update to KDE4 that way but alas, that's when the problem occured.
As mentioned earlier I tried formatting with EXT2 and EXT3 and EXT4 but no joy but FAT32 and NTFS worked fine! Thats what's so odd, normally (in my experience anyway) when this happens the disk just won't format regardless of what type of formatting is chosen so to accept FAT/NTFS but not any linux flavour is just plain weird...
I then deleted/removed the "old" Ext3 partition and also deleted/removed the WinXP Partition and tried partitioning that larger partition to EXT3 but again no luck!
I will give your option a whirl and make the partition smaller (what size would you recommend? Is 12GB too small? too big?)
The Disk itself is an Internal SATA Western Digital Caviar SE16 320GB S300 16MB