I can also confirm that Apple will replace your battery for $29 regardless of whether or not it is at 80%.
I was under the same misconception until a few weeks ago. It could be that some of the early reports regarding the battery replacement program gave the impression that it only applied to batteries with 80% or less capacity remaining, I don't recall exactly. Regardless, the $29 fee gets you a new battery irrespective of the condition of your current battery. Well worthwhile.