If they are an official Apple reseller, then it qualifies or it should actually come with Lion.
If they are not, then the laptop must have been bought from Apple or one of its resellers after June 6, 2011.
EDIT: Anyone got their codes yet? I put my claim in on July 22. Still nothing.