The problem is also that the previous copy of Lion was purchased with another apple ID and the store is aware of that because of the registration of the apple ID. This question/problem is just now starting to come up and I haven't heard a conclusive and definitive answer from Apple, so the best I can recommend is (in order of preference):
Get the original install disks from the seller and/or prompt him/her to contact Apple to have them replaced.
Set up an appointment at your nearest Genius Bar and ask the Genius to figure it out (and then post their suggestions here!)
Buy a retail copy of Snow Leopard (the previous system) disk ($29); use it to erase your drive, install it, update it, and then go back to the store to buy Lion.