> What happens is the second value is negated (__neg__)
> which causes it to become less than timedelta.min and
> that is causing OverflowError.

Yes, and running the test case without C acceleration makes this obvious:

>>> import sys
>>> sys.modules['_datetime'] = None
>>> from datetime import *
>>> timedelta(999999999, 86399, 999999) - timedelta(999999999, 86399, 999998)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "Lib/datetime.py", line 488, in __sub__
    return self + -other
  File "Lib/datetime.py", line 501, in __neg__
    -self._microseconds)
  File "Lib/datetime.py", line 426, in __new__
    raise OverflowError("timedelta # of days is too large: %d" % d)
OverflowError: timedelta # of days is too large: -1000000000

Attached patch fixes the issue.  I would like to think some more about C int overflow before committing.