Yes, I was afraid of something like that from your initial description.
Looking at that, you've re-formatted the first 20 Gig or so of the disk. On a normal install that'd be a XP partition - maybe
the XP partition. Almost certainly you have trashed the meta-data of the (NTFS ?) partition(s) - to locate the data (as in files) will require scanning the drive. Normal suggestions under Linux are Testdisk and photorec (does many file types not just photos). Both from the same people
here - plenty of posts here on LQ about both.
You may be lucky with the files in the unallocated area - in the Linux partition, it's unlikely you'll get much/any back.
A forensic tool called foremost is also useful.
Seems there are also free Windows based tools that work; haven't tried any myself.
Be prepared to spend a
lot of time on recovery - potentially days to weeks.
Forgot the new partition question - gparted is a GUI PartitionManager lookalike; should be available under Ubuntu.