É, garimpei tudo que podia na internet e não consegui solução para gerenciar o iShuffle pelo Ubuntu. O que me restou fazer foi virtualizar o windows XP e instalar o iTunes. Instalei a última versão e, como alguém já sem esperanças de algo, não me impressionei em não funcionar. Baixei a versão 9.0.2 e instalei no windows virtualizado, foi tudo OK!
Recomendo então, para quem passa por problemas com sincronização de iPods com VoiceOver (em especial o iPod Shuffle 4G), que experimente o VM (no site oficial há o .deb para o Ubuntu 10.04) com windows XP virtualizado e iTunes 9.0.2 instalado. Aqui funcionou!