You made a slight mistake that got you confused: you should have deleted the partitions and only format the 2 you installed Windows (35) and your documents (85) on. Then you would have seen a slightly different image for gparted (where it would state 'empty' for sda1).
Install Ubuntu on sda1 by deleting sda1 and formatting it to ext4 (or less preferred ext3) where you divide sda into 3 parts: / (something like ... 10 Gb), swap (2 Gb) and /home (18 Gb)). (you will thank me someday for suggesting a separate partition for /home ;) )
So to answer the question: Or, all my fears are baseless and I should just go on with the installation? is the correct one. But you might need to fix something in grub to get Windows back. The fixmbr will remove grub and therefor Ubuntu from the boot list.
First, there's no such thing as a "partition... which is... unallocated space." A partition is, by definition, allocated space. If you deleted or shrank a partition, the result is unallocated space. Although I believe I understand your meaning in this case, miscommunication on this score can lead to a lot of wasted effort as two parties communicate at cross purposes.
Second, although it's OK to shrink partitions in Windows in preparation for installing Linux, you should never create a partition using the Windows tools with the intention of using it in Linux. Doing so may work if you're lucky, but if you're not lucky, Windows will implement its proprietary Logical Disk Manager (LDM) system, and you'll have to jump through hoops to undo this change before you can install Linux. I don't believe this accounts for your problem, but it bears mentioning.
My suspicion is that you're using an older Master Boot Record (MBR) partitioning scheme and have run into a partition table difficulty. There are several things that can cause this type of problem. Many of them can be fixed with my FixParts program. See its documentation, and this page I've written on the topic. If you still have problems, post back with more detail, such as the output of the following commands, typed in a Linux terminal from an emergency disc:
fdisk -l /dev/sda
parted /dev/sda print
gdisk -l /dev/sda
If you use Ubuntu, precede each of those commands by sudo; with other emergency discs or distributions, be sure you log in as root. (Logging in as root is standard with most Linux emergency discs.) If you use Ubuntu, you'll probably have to install gdisk by typing sudo apt-get install gdisk, too. Edit your original question to include the output of these commands.
Best Answer
There should be an "Install alongside Windows" option and I think you know that, but it's not showing. That may be a problem but immediately, to get Ubuntu safely installed isn't too hard:
This should get you to a point where you can boot into Ubuntu. There is a possibility that because that installer couldn't find Windows, that there will be no option to boot to Windows from within the Grub boot menu. If that's the case you might want to run Boot Repair to fix things up.