I hooked up two new external hard drives, NO PROBLEMS, well up until the second was formatting and we got hit with a power failure! Computer was on a backup, but not the external hard drives as of yet. That stupid message drove me nuts! I looked everywhere and there was not an answer I could find. Hence, since my computer also had a 'clone' drive installed (incase I wreck this one) I started tinkering. (I also tried the clone drive, IT SAW IT and would access it). I figured since after four hours and 2:00 a.m. that I would try Acronis in the morning. (Okay, the reason I didn't clone back, was due to the fact that at that point in time, I had not been able to do a successful clone. Took my tech 3 hours for this simple 15 minute operation since there was something obviously amiss.)
I turned the computer on went to the storage/disk management and got the same natty message. For some strange reason, I checked the system tray thing, the right hand side, where the little "Safely Remove Hardware" icon is. I double clicked on that and found that my one drive was fine, but the other one had been 'stopped'!? I can't remember why I did not tell it to enable there (it might have refused), but I went to Control Panel/System/Device Manger scrolled down through there and found 'storage devices' that shouldn't have ought to have been there! I checked that out and it was showing a "generic" storage devise. I don't have GENERIC, I have Western Digital and the computer verified that the other two were Western Digitals. So I told it to enable it there.
Then guess what I did? I rebooted again, just because.
Then I did the Start/other click (right) on My Computer/Manage/Disk Management and I think it had decided on it's own drive letter moved my CD Rom do another letter, and by that point let me partition and format it and it has been working fine ever since.
Not sure if this is the right answer, but my problem was identical. (Granted I don't have a clue about Ubuntu), but the error message was the same, couldn't partition, format, changed the drive letter, rebooted and rebooted... and kept getting that message.
If that doesn't work and since it doesn't already work, the next thing I would try is to stop the drive from the little system tray "Safely Remove Hardware" thingy, then reboot, then go through the ordeal of enabling it.