Ideal:
Start with an empty list; whenever given a new input, generate a random element
of $\:\{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$,$\:$ and output it and add the pair of that input and that output to the list;
whenever given an previously seen input (as determined by looking at the list),
give the same output as was previously given for that input.
Hybrid_I :
Start with an empty list; whenever given a new input, repeatedly generate random
elements of $\:\{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$ until obtaining one that was not previously given as output,
and output that element; whenever given a previously seen input (as determined
by looking at the list), give the same output as was previously given for that input.
Hybrid_R_(pad) :
Hybrid_R_(pad) is the composition of Hybrid_I with $\:$pad$\:$.
Real(pad) :
Choose a random key $r$, and then act as $\: x\mapsto \operatorname{AES}(r,\hspace{-0.01 in}x) \:\:$.
(Obviously, the hybrids only make sense for up to $2^{128}$ queries,
and Real(pad) only makes sense if $\:\operatorname{Range}(\hspace{.01 in}\text{pad}) \subseteq \{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128} \;$.)
As long as Hybrid_I makes sense, the difference between Ideal and Hybrid_I only matters
when the randomly chosen elements of $\:\{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$ repeat. $\;\;$ (See birthday attack.)
The probability of that happening with at most $q$ queries is at most $\:\frac{\binom{q}{2}}{2^{128}}\:$ (see binomial coefficient).
For all $q$, $\;\;$ if $\:0< q\:$ then $\:\frac{\binom{q}{2}}{2^{128}} < \frac{q^{\hspace{.01 in}2}}{2^{129}}\:\:$.
Since Hybrid_I is symmetric with respect to its inputs,
Hybrid_R_(pad) will behave identically to Hybrid_I whenever $\:$pad$\:$ is injective and Hybrid_I makes sense.
For any oracle adversary $\mathcal{A}$ for distinguishing Real(pad) from Ideal, consider the
oracle adversary $\mathcal{B}$ that applies $\:$pad$\:$ to $\mathcal{A}$'s oracle queries before sending them to the oracle,
forwards the oracle's responses to $\mathcal{A}$, and outputs the same bit as $\mathcal{A}$.
If $\: q\leq 2^{128} \:$ and $\:$pad$\:$ is injective and $\:\operatorname{Range}(\hspace{.01 in}\text{pad}) \subseteq \{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$,
then such a $\mathcal{B}$ uses no decryption and at most $q$ encryption queries to
distinguish AES from a random permutation by an amount that is at most $\:\frac{\binom{q}{2}}{2^{128}}\:$ less than
the amount by which such an $\mathcal{A}$ distinguishes Real(pad) from Ideal.
Therefore, $\:$ if $\: q\leq 2^{128} \:$ and $\:$pad$\:$ is injective and $\:\operatorname{Range}(\hspace{.01 in}\text{pad}) \subseteq \{0,\hspace{-0.04 in}1\hspace{-0.02 in}\}^{128}\:$, $\;$ then
the previous paragraph gives a constructive reduction from an adversary generating at most $q$ keys
that distinguishes Real(pad) from Ideal by $\:\epsilon+\frac{\binom{q}{2}}{2^{128}}\:$ to an adversary making no decryption queries
and at most $q$ encryption queries that distinguishes AES from a random permutation by at least $\hspace{.01 in}\epsilon$,
whose only additional computation is at most $q$ evaluations of $\:$pad$\:$.
As mentioned by CodesInChaos, even if $\:\frac{\binom{q}{2}}{2^{128}}\:$ is large, there's no known
way to take advantage of the distinctness relation between the keys.
