I've also encountered the 'do not remove' message displaying continuously on the ipod after I had updated it. I tried to safely remove the ipod, but this wouldn't work either.
Only been using it a few days after paying £475 for it in the US, not a good start is it.
Thought I'd register my disappointment as from what other users have been saying above, it appears that Apple aren't being very proactive in fixing these problems!