Alright.  So in Python 3.1, this is the behavior:

>>> BaseException().message
(attribute error)
>>> BaseException("foo").message
(attribute error)
>>> BaseException("foo", "bar").message
(attribute error)
>>> x = BaseException()
>>> x.message = "foo"
>>> x.message
'foo'
>>> x = BaseException("foo")
>>> x.message = "bar"
>>> x.message
'bar'
>>> x = BaseException("foo")
>>> x.message = "bar"
>>> x.message
'bar'

So I propose the following as the new behavior for 2.x:

>>> BaseException().message
(deprecation warning)
''
>>> BaseException("foo").message
(deprecation warning)
'foo'
>>> BaseException("foo", "bar").message
(deprecation warning)
''
>>> x = BaseException()
>>> x.message = "foo"
>>> x.message
'foo'
>>> x = BaseException("foo")
>>> x.message = "bar"
>>> x.message
'bar'
>>> x = BaseException("foo", "bar")
>>> x.message = "baz"
>>> x.message
'baz'

Summarized: emit a warning when the same code in Python 3.1 would raise
an exception; let all other cases pass.

There is one other case that I would think about changing, but I don't
see how it can, given the behavior that is implemented in 3.1 already. 
BaseException("a message") is a Python 2.5-supported way of creating an
exception with a value for its message attribute.  This no longer works
in Python 3.1.  So, arguably, this is another case where a deprecation
warning should be emitted.  However, this would be pretty obnoxious,
since BaseException("a message") in Python 2.4 (by way of Exception("a
message"), of course, since Python 2.4 did not have BaseException) was
perfectly valid.  It seems like BaseException(string) should have been
deprecated and BaseException(tuple) been made the preferred API.  That's
for another time, though.

How does the above proposed deprecation behavior sound?