Chances are the disk used to be a GUID Partition Table (GPT) disk. Such disks have partitioning data from sectors 0-33 (typically) and also in the last 33 sectors of the disk. If a GPT disk is repartitioned by a GPT-unaware utility, that utility is likely to replace just sector 0 (the MBR), leaving most of the GPT data intact. Technically, the disk is then an MBR disk; however, some partitioning tools, including many Linux tools that are based on libparted (including GParted) become confused by this. They may show the disk as being completely blank or show the old GPT partitions rather than the new MBR partitions. This is a bug in libparted, but it's triggered by some inconsistent data on the disk.
The solution is to wipe the old GPT data. This can be done various ways, but the simplest is probably to use FixParts, which is designed for this and some other partition table repair tasks. Alternatively, you could use dd to wipe sector 1 (numbered from 0) and the final sector on the disk; that's where the GPT signatures that are confusing libparted reside.
Sorry I didn't get here sooner, Mehrdad. My guess is that when you rewrote the partition table you also wiped out the boot loader in the MBR. Re-installing your boot loader should fix that problem. It's possible that you wrote the wrong partition table, though, which would be harder to fix.