I am Alex who posted above. I fixed my problem so I figured I'd write out my solution in case anyone runs into the same thing.
First, for completeness, I'll mention that the Ubuntu disk utility was giving me extremely weird information that I didn't include in my first post: it showed two 438GB partitions one after the other on a 500GB hard drive. After the second 438GB partition, there were two unformatted partitions.
The solution to my problem was to download Ubuntu Rescue Remix 10.10, burn the liveCD and run the testdisk tool. Here is a walkthrough (pretty much the same as http://www.cgsecurity.org/wiki/TestDisk_Step_By_Step):
sudo -s
testdisk /list
testdisk
In testdisk, I went with "no log", then chose my drive, chose "intel" which was the right type for my PC, then "analyse" and "quick search". I was very disappointed to see the results returned by quick search -- only the very first partition, the recovery partition on my PC, could be saved (check each partition by selecting it and pressing p, if the files on the partition are readable it is recoverable). That is why I went on to choose "deeper search".
"Deeper search" was the holy grail, as it found the other two partitions in working order as well! I checked them by pressing "p" and the partitions were readable. I changed each of them from "D" (deleted) to "P", marked my boot partition as "*" and finally pressed Enter, then "write" and wrote the restored partition table.
Note: to save time, you can interrupt the deeper search after you think it has found what you are looking for. I knew the first 3 partitions started before cylinder 2000, so they had been discovered by then and I stopped the search. I didn't care about the fourth partition.
I just solved it, and I'll post the answer here in case someone else faces a similar problem.
I was unable to resize the partition because my swap space was still in use, so I found out I could disable it using swapoff -a.
After doing this, GParted allowed me to merge the unallocated space with the fedora logical partition. I then right clicked on the logical partition and selected the Check option.
Finally, I used the following to actually allocate the free space to the root and home partitions:
lvextend -L +20G /dev/fedora/home
lvextend -L +20G /dev/fedora/root
resize2fs /dev/fedora/home
resize2fs /dev/fedora/root
Best Answer
It turns out my laptop somehow was given two partition tables an MBR and a GPT, which confused Gparted. The Ubuntu and Fedora installers use Gparted to prepare the drive for installation.
Clearing the GPT with Gdisk for windows fixed the situation. Both Windows and Gparted can read my drive now.
http://sourceforge.net/projects/gptfdisk/
http://www.rodsbooks.com/gdisk/gdisk.html