Reboot and Reinstall OSx Lion with Snow Leopard currently installed on the Mac

You'll need to make your own bootable DVD/USB of the Lion installer to do so. This can be made from the AppStore download and is documented well by OSXDaily.

Lion USB Installer
Lion DVD Installer

Then hold ALT at system boot (before chime & Apple logo) and select your install volume.

Any time you have problems starting a mac with an installer - do check these three articles:

• Finding your Mac OS X version and build information
• Mac OS X versions (builds) for computers
• http://support.apple.com/manuals/# - enter your serial number on the page or in place of the # in the URL to determine the exact model of your mac.

In your case - you probably have a MacBook Pro (Early 2011) which will boot from (Mac OS X v10.6.6 Build 10J567) or later. You might see the term "retail disk" which means it has drivers for all Macs that can run that level of OS - this is different from the disks that ship with macs - you almost never can use say a MacBook Air restore disk on a MacBook Pro - they just have the drivers for that one model.

Normally, you could just buy a retail copy but the last 10.6 retail copy I've seen documented is 10.6.3 and is too old. You'll need to order a replacement disk through AppleCare online or via phone (or find someone in possession of your MacBook Pro's install media for Snow Leopard)

Most Apple Retail stores are set up to image your mac from the factory builds through the genius bar and since your mac is so new, I can't imagine the seller you bought it wouldn't bend over backwards to make sure you got a copy of the appropriate disk (they might even have a service desk that could assist you)