The patch looks reasonable.  I built on it with the following changes:

   1. Added some extra test cases to cover Unicode format strings, 
      since the code was changed to handle these as well.
   2. Changed test_builtin.py by 
      s/m[0].message.message/str(w[0].message)/, since 
      BaseException.message was deprecated in 2.6.

I also have the following general comments:

   1. PEP 3101 explicitly defines the string conversion for 
      object.__format__.  What is the rationale behind this?  Should
      we find out before making this change?
   2. I don't think the comments in 'abstract.c' and 'typeobject.c'
      explaining that the warning will eventually become an error are
      needed.  I think it would be better to open separate issues for
      these migration steps as they can be tracked easier and will be 
      more visible.
   3. test_unicode, test_str have cases that trigger the added 
      warning.  Should they be altered now or when (if) this becomes 
      an error?