iPod 30GB Important Reformat Question

I have a 30GB video ipod. I bought it when i only owned a dell laptop. So the first time i plugged it in formatted it for "Windows".
Now i own 2 newer macs, an iMac, and a SR Macbook. When i plug my ipod into either computer it says that only Macintosh formatted iPods can be updated.
I would love to be able to reformat it to macintosh but i cant figure it out. I have tried to "restore" but that doesnt work.
Would disk unitiliy change anything? im not worried about losing anything, because i have all the music on the harddrive i just want to format it for a mac.
Can anybody help me????

Thanks Guys,
-Adam

I could type a bunch of stuff, but I think Apple says it better. I think this link should do it:

http://docs.info.apple.com/article.html?artnum=61672