The problem is that your object has scaled in object mode, but the transformation has not been applied.
Take this perfectly regular cube for example:
Look at the scale section on the panel:
Switch to Object Mode, select your object and press Ctrl A and select Apply Scale
