HFS+ with journaling enabled is how the drive should have been formatted before use. You may need to reformat it, which will wipe everything from the drive.
Partitioning a hard drive:
To resize (or delete) an existing partition without losing data, you will need to use, for example, iPartition:
No, that's the same thing, I read many reports on this trying to figure out the problem, there were many with your same error & they also had the correct HFS+ journaled/"Mac OS Extended (journaled)".
Only fix I found was a dangerous sounding Terminal method, & I wasn't even sure which version of OSX it was for.
Yes, that's a good idea..
Get carbon copy cloner to make an exact copy of your old HD to the New one...
Then connect the clone & see if TM says it's alright or not, TM has some strange ideas about Disk UUIDs.
Do you need the TM Backup that's on it now for some reason?
I know this issue is 14 months old, but perhaps someone else will read it in the future. I ran into this problem of needing to resize an external drive and discovered that Mac's Disk Utility program, built into the Mac OS, allows you to do this without losing data or needing to buy additional software.
1. Open Disk Utility and select the root diretory of the external disk you want to resize. (If the disk is partitioned, it will have a subdirectory for each partition.)
2. At the top of the dialog box, select Partition.
> You should see five buttons across the top of the dialog box: First Aid, Erase, Partition, RAID, and Restor
> If you select a subdirectory, rather than the root directory, the Partition option is not displayed, because you can't partition a subdirectory.
3. On the screen you should see the disk split into the different partitions. Select the partition you wish to resize.
4. That partition will be highlighed and the lower right part of the box should have a little triangle-like series of lines. Click and hold this triangle, then drag it down to make the partition larger, or drag it up to make the partition smaller.
5. When you get to the size you want, hit apply.
6. Disk Utility should do its thing and your disk will be resized.
Viola. You are finished.
Take a look at http://macs.about.com/od/applications/ss/diskutilitysize_3.htm for pictures of this process.
.. unless Disk Utility gives you the stupid message about needing a resizable filesystem like HFS+ journalled (when you are already USING HFS+ journalled).
Solution to that scenario is here: http://flarn2006.blogspot.com.au/2010/09/grow-hfs-partition-on-mac-os-x-without. html