yeah that battery most likely fell under the recall. they don't do stuff for free out of the kindness of their hearts. glad it worked out for you. free is always the best price.
The other options are that either the OP forgot that he had bought his computer with AppleCare -or- the guy at the Apple Store made a mistake and either thought that the notebook was under Apple Care or he simply forgot to charge for the repairs. But the recall idea is most likely.