A Tale of Abstractions
There's a lot of confusion about this on the Internet, but the term is quite technical, and according to the Cook paper (referenced in the answer liked to by Greg Burghardt), it essentially boils down to this.
OOP Objects (and the related static typing mechanisms, including classes, abstract classes and interface types) and ADTs represent two different approaches to data abstraction. Cook calls the OOP approach "procedural abstraction" - I'll come back to that later. The two have different strengths and weaknesses.
To understand this, think about the underlying concrete data structures (the representations), the operations on them, and the client code (that calls these operations). The OOP approach makes it easy to add new representations (new derived classes, or new implementations of an interface), as long as you don't change the set of operations. The term for this is the public interface. Don't confuse this with interface types (declared via the interface keyword); in this more broad meaning, the public interface is the set of public members (public methods, properties, fields, events). On the other hand, adding new operations is difficult - you have to hunt down all existing different derivatives and change their implementation details to make sure they all support the changed interface.
This is a "procedural abstraction" in the sense that the public interface defines a contract between clients and different implementations, a contract that abstracts away the actual functions (procedures) that are being called. The interface defines a more generalized notion of an operation - it defines what the operation means, what it does, but not exactly how it does it. When you call a method on an object through a variable of a more abstract type, you are expecting it to do perform this operation (as defined by this contract, and as explained in the documentation), but you don't know for sure which concrete function on which class will get called - the underlying language mechanism dispatches the call for you.
Now, with ADTs, it's a bit different. There's typically a finite, limited set of different representations (different underlying data structures). These are all then deemed to be different forms of the same abstract data type (ADT). It is abstract in the sense that you are arranging things so that you can use these different, concrete data structures to in a way that lets you pretend that it's all the same type. So far, that doesn't sound that much different from OOP. As before, client code never mentions the concrete representations (except when the constructors are called); all of it is written in terms of this ADT. However, the operations on the ADT aren't themselves abstract in the same way OOP operations are. Each ADT function internally provides an implementation for every possible representation. There's basically a switch statement in there, that switches on the concrete type, or if not, then there's some language feature that does roughly the same thing. So, in ADTs, clients can ignore the actual concrete type (concrete representation) because each function has a part that deals with any particular representation, and so is guaranteed to work.
This makes it easy to add new operations - you just add a new functions, and you write a bit of logic for each possible representation, or rely on existing functions and treat the data abstractly yourself. Adding new representations, however, is hard, because you then break the aforementioned guarantee; to maintain it, you have to find all functions on the ADT and implement support for the new case.
That means that even though concrete representations are hidden from client code, they are also a part of the ADT contract when it comes to extensions (to adding new operations).
As with any decoupling, in both cases there's an abstraction in between that represents a certain contract between the two components. They get to be decoupled precisely because they are both coupled to that contract, to the abstraction (which is a more generalized representation of the interaction between the two components). If the contract is broken, so is the decoupling.
You'll encounter ADTs more in functional languages, where the "switch" on the representation happens via pattern matching. But also, primitive types, like float can be considered ADTs as well (though internal to the language), at least in the context of certain operations, because there are different underlying representations - e.g. there are special bit patterns that represent -inf, +inf, NaN, etc., and when you use the normal arithmetic operations, you don't have to examine for these special cases, the operations can handle these by themselves.
It's not all about the type system though; you can use these ideas to design your own abstractions outside of the type system. One example is the Visitor pattern. While it's often described as a way to do multiple dispatch, it can also be seen as an implementation of an ADT: the different Element derivatives are the different representations, and different Visitors are different operations. Note the similarities: it is easy to add new visitors, but since each visitor handles every element, it is hard to add new elements. Another way to do it is to write operations that in terms of handles - instead of an object or a concrete data structure, an operation takes in a handle (e.g., an index of some sort), and then uses it internally to discover the concrete type and find some data structure somewhere. This is probably something you'd do under special circumstances, though - e.g., the motivation may be to increase performance by taking control over how data is stored to ensure cache friendliness.
Finally to answer your question; Iterator, as implemented in Java, is not an ADT in this sense; but in general it should be possible to implement iterators as ADTs.
What part of Iterator in Java doesn't meet the definition?
It's because of the kind of abstraction used here. It's the "procedural abstraction" (the OOP kind of abstraction): the Iterator interface represents a "thing you can iterate over" (a collection), that supports a certain set of abstract operations (most importantly, next and hasNext).
It's easy to add new representations (new implementations of Iterator) - you just implement the interface. Here, "new representation" refers to things like the state that the iterator keeps internally, and the exact details of how it goes about the iteration: you can vary the collection over which it iterates, the order in which it does so, how it keeps track of all of that, etc. And you don't have to make changes to client code, as long as it relies solely on the Iterator interface. Java's foreach loop ("enhanced for-loop") makes use of Iterator behind the scenes; it can work with custom collections if they implement the Iterable interface, which in turn provides the foreach loop with a way to obtain an Iterator.
More to the point, if Java came up with new collections and new iterators for them (new concrete representations of Iterator), that wouldn't affect other people's code - it's just a new option that people can make use of if they want to. If, on the other hand, they changed the foreach loop to require a new operation on the Iterable interface (the assumption here is that there's no reasonable default implementation), than that would be a breaking change - anyone who implemented Iterable & Iterator to provide support for the foreach loop would have to go back and change their code. Hopefully, this gives some context to "easy" vs "hard"; it's not merely about one being more inconvenient then the other for the programmer, but rather about the interaction between the client code and library code in the face of change, especially once the latter has been released "out there". New implementations are adding new behavior, sure, but it within the confines of the abstract operations (it's conceptually the same set of high-level operations), and client code is written in a way that expects this.
