I successfully installed 12.04 on my Lenovo U410 64-bit Windows 8 machine after several failed attempts, and I would like to share my solution to this problem with you:
First, get the live disc for the version of Ubuntu that you want. I installed 12.04 LTS. Windows 8 (in my experience) is usually run on 64-bit machines, so you'll likely need the 64-bit version of 12.04.
Next, put the live disc in your optical drive. Despite what you may expect, you will not be able to successfully boot off of the Live disc because of the firmware called Secure Boot. This is in place to prevent someone from accessing the admin account for Windows 8 and stealing your information. The next step is to get around this firmware.
Next, go into the general settings found under the 'change PC settings' menu. Scroll to the bottom and click the 'Advanced Start-Up' section and click the button that says 'Restart Now'. You will see a waiting screen, and then several options to click on. Click on 'Troubleshooting'. Then click on 'Advanced Options'. Then click 'UEFI Firmware Settings'. Then click on the restart button shown on your screen. This restarts your computer and gives you access to your BIOS.
Use your tab key to get to a tab that says something like 'App Menu'. Then arrow to the option that says Setup and hit enter. You'll then see a blue screen that has several tabs at the top. Go to the 'Security' tab and there will be an option for 'Secure Boot' that should be greyed out. If it's not, then arrow down to it and hit enter, then select 'Disabled'. Otherwise, go through the tabs and look for an option that has the abbreviation 'UEFI' next to it. Change this option to 'Legacy Support'. You should then see an option in the same menu that says 'Boot Priority'. Change this from 'UEFI first' to 'Legacy first'. Then hit the function key that saves and exits the BIOS.
You should now be able to boot from the live disc and install Ubuntu. Enjoy!