Yes, I already read about refit somewhere and will research that further. I think it was about setting up a separate data partition and / or multi boot environments.

Hmm, I have an original Intel Mac, did not realize that this is different. But I don't want to go offtopic here, will continue to read about it.

You can't imagine how many times I put it back to Fat32 now so ext2/3 is not an issue, it was never on the disk. My assumption is that something resistent is put onto that drive since it is a NAS drive and maybe that's what issues the error. However, this would not explain why it also happens to my other standard USB device.

Currently trying to run diskutil in terminal. It states Creating partition map 0% and does not do anything anymore since 10 min now. I guess this won't work either.

If I can't figure it out I'll call Apple Support since I can expect that these things work for that amount of money I spent on it.

Will post a final here if I can figure it out. Thanks so far.

Try one last thing.

Boot-up your OSX DVD with this HDD connected and try format using Disk Utility.app from DVD.

BTW, Apple Support is better there than in Brazil.

That sounded like a good opportunity. Just tried that. Same issue. It seems to delete the FAT32 partition and then hangs up. Again, tried with 2 different USB drives. Booted from DVD. So assuming install DVD is ok, assuming Hardware is ok since I use two different devices (which work fine for everything else) and assuming that I'm not to dumb to select two options I really don't have any clue what's going on.

I noticed one error during all the trials where it stated some path with framework and or boot0 or something like that, I didn't write it down unfortunately. That was earlier when I tried fdisk and diskutil in terminal.

Again, thanks for your support. I will call the Apple Support tomorrow, maybe they have some sophisticated analysis which sheds some light onto this. Will post it here once I know more.

Nice man goodluck with support.

I remember this now, don't use GPT for Time Machine...maybe had hangs...try use only MBR

So I finally sorted it out. After a couple of further attempts using OS X and different tools I started looking for a software which could do it using Linux. I haven't found anything. So I looked further for something using Windows.

Although I don't like it I have to admit that MacDrive 7 on Windows XP did it. It ran just perfect, done in 2 minutes and drive usable for Time Machine without any further issues. It worked even with the Trial Version and I really consider to buy it for any potential future need. I think the only disadvantage is that I have read that MacDrive can only format the entire drive, which I wanted to do anyway. However, some might want to have a separate FAT or NTFS partition on it, I think in that case this might not work.

However, if anyone should have the same issue try MacDrive 7 on XP.