At least in the case of SimpleDB, replaying requests is usually not a problem -- if you Put or Delete an attribute which has already been Put or Deleted, it has no effect.
Sorry, but you aren't thinking like a security professional here. Consider the case, e.g., where you create a domain, delete it and recreate it. An attacker monitoring the deletion can with impunity wipe out your data at a later date.
Ew! They use the timestamp parameter for that? That's both sick and wrong. Requiring people who access your webservice to have an accurate clock is the most braindead thing I've heard this month, at least. Oh boy, network congestion and clock skew could combine to produce some wonderful heisenbugs for developers. And for what? The want of nonce? Some ridiculous design principle of making your API totally state free. sigh
State-free protocols are useful when the server side is distributed and potentially disconnected. :-)
As for "wonderful heisenbugs" -- the AWS services return a clear "hey, your clock is broken" error, so it wouldn't be very hard to developers to figure out what was going on.
Plenty of well-regarded crypto protocols use timestamps to prevent replay. The nonce isn't a panacea; you have any number of design pitfalls to deal with when trying to secure a message with a random number, too.