exarkun@charm:~$ python
Python 2.5.2 (r252:60911, Jul 31 2008, 17:28:52) 
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> int('\0', 256)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 256: '\x00'
>>> int('x', 256)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: int() base must be >= 2 and <= 36
>>> 

The former is misleading. \x00 is a perfectly valid byte if the base is
256. The real problem, that base 256 isn't supported, is obscured. It
would be much better for the latter case's message to be used in the
former case.

Since it is not defined which bytes are used as digits for bases > 36,
\x00 is not a "valid byte".

In any case, the problem here is that the base check is done after the
"no NULL" check. Perhaps the error should explicitly mention that no
null bytes are allowed.

You tested on 2.5.2 but marked this for 2.6.  3.0 gives
>>> int('\0')
Traceback (most recent call last):
  File "<pyshell#0>", line 1, in <module>
    int('\0')
UnicodeEncodeError: 'decimal' codec can't encode character '\x00' in
position 0: invalid decimal Unicode string

>>> int('\1')
Traceback (most recent call last):
  File "<pyshell#5>", line 1, in <module>
    int('\1')
ValueError: invalid literal for int() with base 10: '\x01'

>>> int('\1',256)
Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    int('\1',256)
ValueError: int() arg 2 must be >= 2 and <= 36

The 3.0 doc on string inputs
"A string must be a base-radix integer literal optionally preceded by
‘+’ or ‘-‘ (with no space in between) and optionally surrounded by
whitespace. A base-n literal consists of the digits 0 to n-1, with ‘a’
to ‘z’ (or ‘A’ to ‘Z’) having values 10 to 35."

in much clearer than the 2.6 doc
"If the argument is a string, it must contain a possibly signed decimal
number representable as a Python integer, possibly embedded in whitespace."

Even so, I do not see any inconsistency.

2.6 exhibits the same behavior as 2.5 in this case. 3.0 exhibits
similar behavior, but with a slightly different exception in the NUL
case. The examples included showing the Python 3 behavior don't cover
the same cases as the examples I included in my initial comment.

Python 3 gives same confusing error:

>>> int(b'\0', 999)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 999: b'\x00'

>>> int(b'x', 999)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: int() arg 2 must be >= 2 and <= 36

See also issue bpo-7710.

No more bug with Python 3.2.

On 2.7, we still experience the behavior described in msg75290.

Proposed as won't fix for the 2.x series.