<p>I've seen numerous people mentions that you shouldn't use widths and padding or margins on the same element with CSS. Why is that?</p>

Because some browsers treat the width as the total width of the element including the padding and the margins, and others treat the width as the base width to which the padding and margins are added.  As a result your design will look different in different browsers.
For more information, see the
W3C page on Box Model
and
quirksmode's take
.