I use my 8GB Fuze in the car as well. Hooked up via the headphone jack and it works without problem. As expected with a headphone hookup, the signal is kind of low, but my JVC head unit has an adjustable gain on the aux in to help compensate. Boosting the EQ on the Fuze helps too.
Not to insult your intelligence, but are you sure the cable is inserted all the way in the Fuze? I only ask because I thought I had a problem at first and then realized the cable wasn't all the way in. For some reason the cable I was using required a bit of force to insert all the way into the Fuze the first time. After that, no problems. Oddly, the headphones required no force, it was something specific to the cable.