I have this same problem with my various pedals and the CDP-S350. It needs a "normally open" (aka "NO") pedal, but the simple, cheap Yamaha pedals (I can't find a model number on the one at hand) are "normally closed" (aka "NC").
The Yamaha units I've had have a built-in function that "looks" at the pedal when you first power the unit on, which assumes you are NOT pressing the pedal at startup, to detect whether it's an NO or NC pedal, and then Does The Right Thing after that. The CDP-S350 does not seem to be that smart, and it also does not have any menu function to let you change what it expects.
The CDP-S350 needs a "normally open" pedal, and that's that. (As people have mentioned above, some pedals have a switch that lets you select NC or NO. Get one of these.)
Rob in Seatttle
