> It seems to me that a query saying "SELECT column FROM table WHERE
> column LIKE 'AA%';" should be just as fast or very close to the first
> case up above. However, explain tells me that this query is not using
> the index above, which is what's not making sense to me.
It looks for an exact expression match, and doesn't know about values
which are equal.
You can provide both clauses.
WHERE column LIKE 'A%' and column LIKE 'AA%';