You should also note that "Do Not Connect" will show up whenever the device is being accessed, potentially by the iPodService application running invisibly in the background. If your iPod says "Do Not Connect" that is what this means.
Out of curiousity, what drive letter is your iPod assigned when you connect it? You should be able to find this by double clicking on the "My Computer" icon, it'll look like a device with a slot and should be titled "ipod."