My last phone died in late June/early July of last year, and the first iPhone was missing two features I wanted, most notably 3G. So I got a Blackjack instead. They put me on a 18 month contract.
Now, I just called AT&T CS today to ask why I wouldn't be eligible, and I told them that if I was going to get the iPhone, I would be upgrading my monthly plan. The rep talked his manager (I doubt he actually did) and said that if I converted to a new plan now they could make me upgrade eligible. So I converted to a plan for the same price, but on the AT&T Nation plans, I used to have a really old plan. Now I'm set to go on July 11th. They didn't renew my contract yet, they will do that on the 11th.
Moral of the story: If you aren't eligible, call them, and tell them you want to spend more money. They will most likely take care of you.