Q: I just purchased Lion and attempted to install...

Do you have a Boot Camp Windows partition on your drive?

Do you have any other partitions on your drive?

Are you trying to install on a RAID?

Let's start by:

Repair the Hard Drive and Permissions

Boot from your Snow Leopard Installer disc. After the installer loads select your language and click on the Continue button. When the menu bar appears select Disk Utility from the Utilities menu. After DU loads select your hard drive entry (mfgr.'s ID and drive size) from the the left side list.  In the DU status area you will see an entry for the S.M.A.R.T. status of the hard drive.  If it does not say "Verified" then the hard drive is failing or failed. (SMART status is not reported on external Firewire or USB drives.) If the drive is "Verified" then select your OS X volume from the list on the left (sub-entry below the drive entry,) click on the First Aid tab, then click on the Repair Disk button. If DU reports any errors that have been fixed, then re-run Repair Disk until no errors are reported. If no errors are reported click on the Repair Permissions button. Wait until the operation completes, then quit DU and return to the installer.

If DU reports errors it cannot fix, then you will need Disk Warrior and/or Tech Tool Pro to repair the drive. If you don't have either of them or if neither of them can fix the drive, then you will need to reformat the drive and reinstall OS X.

While you have Disk Utility open check to see how many volumes are listed in the sidebar for your drive. I would only expect to find Macintosh HD (if you haven't renamed it.)

Also, where is the Lion installer application? If it's still in your Applications folder I suggest you make a copy of it in your Downloads folder for safe keeping. Also, see:

Make Your Own Lion Installer

1. After downloading Lion you must first save the Install Mac OS X Lion application. After Lion downloads DO NOT click on the Install button. Go to your Applications folder and make a copy of the Lion installer. Move the copy into your Downloads folder. Now you can click on the Install button. You must do this because the installer deletes itself automatically when it finishes installing Lion.

2. Get a USB flash drive that is at least 8 GBs. Prep this flash drive as follows:

1. Open Disk Utility in your Utilities folder.
2. After DU loads select your hard drive (this is the entry with the mfgr.'s ID and size) from the left side list. Note the SMART status of the drive in DU's status area.  If it does not say "Verified" then the drive is failing or has failed and will need replacing.  SMART info will not be reported  on external drives. Otherwise, click on the Partition tab in the DU main window.
3. Under the Volume Scheme heading set the number of partitions from the drop down menu to one. Set the format type to Mac OS Extended (Journaled.) Click on the Options button, set the partition scheme to GUID then click on the OK button. Click on the Partition button and wait until the process has completed.
4. Select the volume you just created (this is the sub-entry under the drive entry) from the left side list. Click on the Erase tab in the DU main window.
5. Set the format type to Mac OS Extended (Journaled.) Click on the Options button, check the button for Zero Data and click on OK to return to the Erase window.
6. Click on the Erase button. The format process can take up to several hours depending upon the drive size.

3. Locate the saved Lion installer in your Downloads folder. CTRL- or RIGHT-click on the installer and select Show Package Contents from the contextual menu. Double-click on the Contents folder to open it. Double-click on the SharedSupport folder. In this folder you will see a disc image named InstallESD.dmg.

4. Plug in your freshly prepared USB flash drive. You are going to clone the InstallESD.dmg disc image to the flash drive as follows:

1. Open Disk Utility.
2. Select the USB flash drive from the left side list.
3. Click on the Restore tab in the DU main window.
4. Check the box labeled Erase destination.
5. Select the USB flash drive volume from the left side list and drag it to the Destination entry field.
6. Drag the InstallESD.dmg disc image file into the Source entry field.
7. Double-check you got it right, then click on the Restore button.

When the clone is completed you have a fully bootable Lion installer that  you can use without having to re-download Lion.

I rad somthing the other day where someone had to make the partition a little smaller to get Lion to install.

The error wasn't the same as yours. It was somthing like "OS X can't be install on this drive". Once they shrunk the partition by about 100MB or 1 GB Lion installed then expanded the partition again to get that space back.

Download LionDiskMaker and use that yo make your USB installer.