diff -r e0eb7dea245f Lib/test/test_format.py
--- a/Lib/test/test_format.py	Mon Jul 30 04:07:49 2012 -0700
+++ b/Lib/test/test_format.py	Tue Jul 31 14:43:57 2012 -0600
@@ -2,6 +2,7 @@
 from test.test_support import verbose, have_unicode, TestFailed
 import test.test_support as test_support
 import unittest
+from _testcapi import _test_formatstringType
 
 maxsize = test_support.MAX_Py_ssize_t
 
@@ -234,6 +235,10 @@
         testformat('%g', 1.1, '1.1')
         testformat('%#g', 1.1, '1.10000')
 
+        # Regression test for http://bugs.python.org/issue15516.
+        fst = _test_formatstringType()
+        testformat("%x", fst, '0')
+
         # Test exception for unknown format characters
         if verbose:
             print 'Testing exceptions'
diff -r e0eb7dea245f Modules/_testcapimodule.c
--- a/Modules/_testcapimodule.c	Mon Jul 30 04:07:49 2012 -0700
+++ b/Modules/_testcapimodule.c	Tue Jul 31 14:43:57 2012 -0600
@@ -1901,6 +1901,91 @@
 };
 
 
+static PyObject *
+test_formatstring_int (PyObject *self)
+{
+  return PyErr_Format (PyExc_RuntimeError, "can't convert to int");
+}
+
+static PyObject *
+test_formatstring_long (PyObject *self)
+{
+  /* This checks for the bug we are testing.  PyString_Format used to
+     call PyNumber_Long without clearing a previous error.  So, if we
+     reach here and the error is set, we "re-throw".  */
+  if (PyErr_Occurred ())
+    return NULL;
+  return PyLong_FromLong (0);
+}
+
+static PyNumberMethods test_formatstring_as_number = {
+  NULL,
+  NULL,
+  NULL,
+  NULL,
+  NULL,
+  NULL,				/* nb_divmod */
+  NULL,				/* nb_power */
+  NULL,				/* nb_negative */
+  NULL,				/* nb_positive */
+  NULL,				/* nb_absolute */
+  NULL,				/* nb_nonzero */
+  NULL,				/* nb_invert */
+  NULL,				/* nb_lshift */
+  NULL,				/* nb_rshift */
+  NULL,				/* nb_and */
+  NULL,				/* nb_xor */
+  NULL,				/* nb_or */
+  NULL,				/* nb_coerce */
+  test_formatstring_int,	/* nb_int */
+  test_formatstring_long,	/* nb_long */
+  NULL,				/* nb_float */
+  NULL,				/* nb_oct */
+  NULL				/* nb_hex */
+};
+
+static PyTypeObject test_formatstringType = {
+    PyObject_HEAD_INIT(NULL)
+    0,                          /* Number of items for varobject */
+    "_test_formatstringType",	/* Name of this type */
+    sizeof(PyObject),           /* Basic object size */
+    0,                          /* Item size for varobject */
+    (destructor)PyObject_Del, /* tp_dealloc */
+    0,                          /* tp_print */
+    0,                          /* tp_getattr */
+    0,                          /* tp_setattr */
+    0,                          /* tp_compare */
+    0,                          /* tp_repr */
+    &test_formatstring_as_number, /* tp_as_number */
+    0,                          /* tp_as_sequence */
+    0,                          /* tp_as_mapping */
+    0,                          /* tp_hash */
+    0,                          /* tp_call */
+    0,                          /* tp_str */
+    PyObject_GenericGetAttr,  /* tp_getattro */
+    0,                          /* tp_setattro */
+    0,                        /* tp_as_buffer */
+    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_CHECKTYPES,	/* tp_flags */
+    0,                          /* tp_doc */
+    0,                          /* tp_traverse */
+    0,                          /* tp_clear */
+    0,                          /* tp_richcompare */
+    0,                          /* tp_weaklistoffset */
+    0,                          /* tp_iter */
+    0,                          /* tp_iternext */
+    0,                          /* tp_methods */
+    0,                          /* tp_members */
+    0,                          /* tp_getset */
+    0,                          /* tp_base */
+    0,                          /* tp_dict */
+    0,                          /* tp_descr_get */
+    0,                          /* tp_descr_set */
+    0,                          /* tp_dictoffset */
+    0,                          /* tp_init */
+    0,                          /* tp_alloc */
+    PyType_GenericNew,                  /* tp_new */
+};
+
 PyMODINIT_FUNC
 init_testcapi(void)
 {
@@ -1918,6 +2003,13 @@
        test_capi to automatically call this */
     PyModule_AddObject(m, "_test_structmembersType", (PyObject *)&test_structmembersType);
 
+    Py_TYPE(&test_formatstringType)=&PyType_Type;
+    Py_INCREF(&test_formatstringType);
+    PyType_Ready(&test_formatstringType);
+    /* don't use a name starting with "test", since we don't want
+       test_capi to automatically call this */
+    PyModule_AddObject(m, "_test_formatstringType", (PyObject *)&test_formatstringType);
+
     PyModule_AddObject(m, "CHAR_MAX", PyInt_FromLong(CHAR_MAX));
     PyModule_AddObject(m, "CHAR_MIN", PyInt_FromLong(CHAR_MIN));
     PyModule_AddObject(m, "UCHAR_MAX", PyInt_FromLong(UCHAR_MAX));
diff -r e0eb7dea245f Objects/stringobject.c
--- a/Objects/stringobject.c	Mon Jul 30 04:07:49 2012 -0700
+++ b/Objects/stringobject.c	Tue Jul 31 14:43:57 2012 -0600
@@ -4489,7 +4489,10 @@
                     }
                     else {
                         iobj = PyNumber_Int(v);
-                        if (iobj==NULL) iobj = PyNumber_Long(v);
+                        if (iobj==NULL) {
+			    PyErr_Clear();
+			    iobj = PyNumber_Long(v);
+			}
                     }
                     if (iobj!=NULL) {
                         if (PyInt_Check(iobj)) {