One possible solution:
I just had the same problem with an external USB disk that I tried to repartition. No matter what I did (using diskutil and dd in the Terminal, ...) I couldn't get rid of the error.
But then I plugged it into a Linux box and partitioned it there without any problems.
When I plugged the disk back into the Mac, I could format the linux-created partition with Journaled HFS+. Problem solved!
Another possible solution:
I managed to create a single partition on the entire disk by running this command:
diskutil eraseVolume jhfs+ "Volume Name" /dev/disk# [substitute # with your disk number.]
To get the disk number you need to run "diskutil list" and identify this disk's number from the listing.
Last possible solution:
Format the disk using all 0's. This is a Security Erase. It takes a lot of time. Not the best thing to do to an SSD but may be required.