Ok and you used the same Apple ID that you bought Lion with?
What model year is your Mac? If it is an "Early" Early 2011 model that came with snow leopard you can't (TYPO, Should of READ CAN'T) use the Online Internet Recovery system as that is only for Mac computers that Originally came with Lion or Mt Lion. Even though the system started from it it will never work for you as your system came with Snow Leopard or Leopard.
You must use the original systemdiscs to reinstall Snow Leopard then once that is installed and updated to 10.6.8 then you login to the Mac App store to redownload Lion and install it.
I could give you the full story on why your system is booting from the Online Internet Recovery system and why it isn't working but just take my work for it you will never get Lion installed from that.
Once you have completed the Snow Leopard install, and I suggest you first reinstall the iLife apps from the second system disc, the Applications disc, before you upgrade to Lion, and then download and install lion use the Lion Recovery Disk Assistant program to make a USB thumb drive of the Built in Recovery HD partition so in the future you will be able to boot the system and reinstall Lion Clean, IE without first installing Snow Leopard.