I am considering buying the Sansa Fuze, but I read somewhere that It will only connect

to a PC running under Windows. Is this correct, or can I also connect it to a Linux machine?

You can use it with a Linux machine. You just have to set the USB mode of the player to MSC.