I think a pair of integers is a poor API.  It ties the value of the fractional part to nanoseconds.  What happens when a future filesystem implements picosecond resolution?  And then later goes to femtoseconds?  Or some platform chooses another divisor (2**32)?  This should all be abstracted away by the API, as the current API does.  Otherwise you start sprinkling magic values in your code (ie 1e9).  Suggesting that other representations (float128, Decimal) can be built on top of the (int,int) interface is irrelevant; obviously, any representation can be built on top of any other.

I think Decimal is reasonable, except that it breaks existing code.  One cannot perform computation between a Decimal and a float, so almost any existing manipulations of atime/utime would start throw exceptions.

I suggest that a float128 type would solve the problem on all counts--nobody would have to change their code, and it would handle nanosecond (or I think even zeptosecond!) resolution.  And when we run out of resolution, we can switch to float256.  (Or an arbitrary-precision float if Python has one by then.)

os.stat added support for float atime/mtime in 2.3, specifically in October 2002:
  http://hg.python.org/cpython/rev/0bbea4dcd9be
This predates both the inclusion of Decimal in Python (2.4) and nanosecond resolution in the utime API (2008).  I could find no discussion of the change, so I don't know what other representations were considered.  It's hard to say what the author of the code might have done if Decimal had existed back then, or if he foresaw nanosecond resolution.

However, that author is already present in this thread ;-)  Martin?