What version are you running and what fields do you have required?

As odd as it might sound, prior to 7.2, the common problem for this was that people would forget to click the "I agree" to the form rules checkbox.