どうやら、WindowsのシステムドライブがC以外になっているため、WindowsにShuffleが認識された際にCドライブになってしまうことが原因らしい*1。
USBメモリをもう1つさして、そちらをC、ShuffleをDになるようにしたら認識できた...
http://k.bsdlab.org/archives/2005/04/apple_ipod_shuf.html
http://docs.info.apple.com/jarticle.html?artnum=93426
*1:先日のWindowsXP再インストールの際に、手違いでシステムドライブがHになってしまった