You could try another hard drive utility program. I've long since lost track of any names as I've always been able to use Disk Utility. Of course, I've never wanted to render my iPods unusable as iPods by partitioning them so I've never tried.
I'd do a google search for Drive formatting software (Drive 10?). Or, just use it as is.
Did you try formatting it as a HFS disk and then partitioning? Did you try restoring it using iTunes and then formatting it? I don't know what else to suggest.
I've heard very mixed reports about getting it to go back to a functioning iPod, hence my repetition. I tend to be cautious.