Good advice Jiver. A couple of other things to add...
Slow and Simple IS highly recommended. I've started with Foxtrot and Rumba music--with very pronounced beats. I like the Waltz, but the whole three-count vs. four count thing usually throws the newer dancers.
An exercise I've used with good success to help other dancers:
-- Locate the "accent" beat (i.e., the first beat on the measure) of a slow fox or rumba. Clap your hands when you hear this first beat, then start counting 1(clap), 2, 3, 4, 1(clap) 2,3,...
-- When comfortable with the clapping, start walking (in a circle, or straight forward, or backward, whatever feels right). One step for every beat heard. Clap only on the first beat--for accent.
This teaches how to listen for the beat, and more importantly, react to it, while clapping accentuates the first beat. After this you can graduate your newbies to intermediate counting by walking with half-beats (1&2&3& etc.) and then musical structure. But that's a discussion for another day.
my two cents...