First, try sudo -l on any system as any user and get a list of things (if any) that you are allowed to do. Check and see if anything is missing.
The sudo mailing list also hinted to a way to parse the sudoers file to see if anything is malformed. This can verify at the sudoers does not contain any typos or syntax errors.
Finally, and most importantly, know this:
"When multiple entries match for a user, they are applied in order. Where there are multiple matches, the last match is used (which is not necessarily the most specific match)."
So order matters!!! Start with general rules and become most specific towards the end of the sudoers file. If you grant something at the top and deny it at the bottom, sudo won't allow it for the reason above. In that case, change the order but be careful not to open (i.e. grant) too much by doing so.