Okay, I'm getting a grasp on what the bug actually is and what needs to be fixed.
Table operations like clone table and create table currently throw a TableNotFoundException, wrapped in a RuntimeException (because they're not technically supposed to happen (we should be throwing an AssertionError here, not a RuntimeException, anyway), but do, because we're re-using the ThriftTableOperationException to return a NOTFOUND code, which is interpreted as a TableNotFoundException).
I will fix this.
I could not find the importTable problem John Vines was referring to.
I don't think this problem extends beyond clone and create, because in all other cases, we're only looking for an existing fully-qualified table, and it doesn't really matter why the table doesn't exist. In fact, it shouldn't even have to reveal more information than necessary (like the fact that a namespace exists or doesn't exist) when the fully-qualified table doesn't exist.