I feel dumb I just started a thread about this same problem I'm having.
restoring to factory settings won't make it update on a Mac - it shipped from the Factory as a Windows-formatted iPod, restoring settings only puts it back to the way you bought it new.