
3 answers
The users in question will have the "Customize Application" permission on their profile.
http://help.salesforce.com/HTViewHelpDoc?id=fields_defining_field_validation_rules.htm&language=en_US
What profile do you have assigned to the users in questions?