Short answer: because RFC 3280, its predecessor, says so.
Longer answer: because historically ASN.1 encoders/decoders have had problems with properly encoding and decoding integers.
X.509 uses DER encoded ASN.1, which amongst other things, means that the data must be encoded in its minimal (shortest) form. As integers are stored in a variable length twos-complement form, in order to properly encode a non-negative integer which happens to have its leading bit (MSB) set, it must be padded with a leading zero, which in other circumstance is disallowed.
The wording of X.690(http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf )
is such that the leading 9 bits of an integer must be inspected in order to verify the minimal form, thus allowing such positive integers to have leading 0 byte.
To quote Peter Gutmann
There's a second but: Historically many encoders have gotten the signedness of
integers wrong, which means that (a) if you get a negative number (at least in
the area of crypto, which I'm most familiar with) it's always an encoding
error and never a deliberate use of a negative value, and (b) because of the
widespread use of incorrect encoders, many decoders treat all integer values
as unsigned. So while you can use negative values in theory, it's not a good
idea in practice.
The correct determination of serial numbers is critical when it comes to revocation checks. Ambiguity is an enemy.
It seems to me that this is exactly the problem your encoder is having...
