Here is a patch based on Matthew's patch. It is smaller (+35 lines vs +59) but fixes error messages for more cases:

int(b'123\0') -- bytes string with null without base.
int(b'123\xbd') -- non-utf-8 bytes string.
int('123\ud800') -- lone surrogate in unicode string.

Unfortunately it is not easy to backport it to 2.7. PyErr_Format() in 2.7 works only with null-terminated strings. I propose to fix this issue on 3.3+ and declare it as "won't fix" for 2.7.