Dear WhyGuy, I had a similar problem as a result of trying to repurpose a Time Machine drive that I was using with a different machine. It seems that Time Machine is savvy enough to realize that I am technically not the administrator (since I pulled it from another machine and tried to erase/reformat the drive). In any case after much pondering and trying different unworkable solutions as a result of simply not being able to change the permissions etc. - I came upon what I think is a pretty novel / basic solution.
I simply opened the disk utility and instead of trying to reformat using Mac OS Extended (Journaled), I just used this 3-step super simple process:
1. Open Disk Utiliity
2. Format the subject Time Machine disk with MS DOS (FAT) selected.
3. Then Reformat the drive using Mac OS Extended (Journaled).
It's that simple. No need for repartitioning, special software, mumbo jumbo.
I hope this helps someone else because it took me about 3 hours of looking at obscure shareware and jacking around before it dawned on me that this solution might work.
Kind regards,
BoulderAndrew