"most of the space on the disk right now is empty, and making a straight image of the disk will include all this empty space. Or is that not true?"
Not true will only back up the used space not empty. When restoring has to be to same size of original partition or larger in size.
"Also, is it possible to backup your paritition table, and re-make the partitions with the same UUIDS so that your fstab file will work when you try to recover?"
I have done clean installs and the uuid's did not change. If I did a clean restore with a new drive. Then the imaging program when restoring would assign those uuids to the new hardrive. As a image restore is a byte-by-byte original copy.
I like Redo backup It's free and 250mb iso to burn a bootable disk. Same as under the hood engine as Clonezilla just as not as difficult or as many features.http://redobackup.org/
Allows me to backup all in one 2 NTFS Win7 & Winxp with mbr, 3 Linux mint partitions. Or can backup the Windows partition separately as a set and then Linux ones as a set. As long as I don't change the partitions then can just restore what's needed instead of full drive backup or restore. Bork my Linux Mint then restore and back up in 30 mins.
Also have installed Ubuntu 12.10 & Fuduntu over mint and then backed those up. Now if I want to try them again can restore them to mints location and run those for awhile. And then restore mint back over those going back to my mint install where I left off.
Clonezilla is another one to consider more flexible and many more fine-tune features. But more difficult to use.
I love Redo as gets the job done and comes with extras and even wifi connection if needed.