I've done this myself - don't have my machine to hand (at work - Vi$ta
... meh!) iirc, I had to unmount them, then use the disk management
utility in the administrative tools section on the menu ... will try
to have a look this evening. The trick was unmounting the filesystem
first - don't think it would let me while it was mounted.

I got them unmounted but didn't see anyway to rename them using
Palimpsest Disk Utility. I got an error when I hit the Change button:
Error setting File System label

Error changing fslabel: helper exited with exit code 1: fstype ntfs not
supported

mine were big (500Gb, 750Gb, 1.5Tb) USB disks
straight off the shelf, so it's not likely that they'd be anything
other than ntfs ...

I'll have to have a look when I get home - see if any bells ring ...

You could try simply going into Nautilus, right clicking on the drive's
icon and selecting 'Rename'. I don't know if this will provide a
permanent solution, however, as I have no external disks to experiment on.

I would boot the Live CD and then use the partition manager to label the
disks. Do not access the disks with a file manager first or you will be
mounting them and you don't want that. If a disk icon appears on the desktop
then you can right-click and unmount from the drop down menu.

You might want to take note of the Linux drive designations (sdb1, sdb2,
etc.) and disk or partition size first so that you don't get them confused
before you re-boot and use the Live CD.

Should I unmount them before I reboot?

linux will unmount them for you during the shutdown/reboot process.