There is an important machine in my department which must be backed up. It uses lvm2 to span its various partitions over two 80G PATA hard drives (lvm tools output: http://pastebin.com/Wh3h9PVz). I have tried using clonezilla to image the drives, but it is being difficult. I may have gotten a good image of it by using the "use dd only" option, however I am having difficulty restoring that image to a new machine. How can I make an image of these partitions such that the filesystem can be recreated on a new machine? Ideally, the solution would include being able to put the filesystem on SATA hard drives rather than PATA.
Because you're using LVM set up on those specific drives, I'm not sure I'd want so much a clone of the system as just a straight backup. Otherwise you might restore to a system that doesn't take kindly to the drive configuration you restore to. Personally the only time I clone things now is if I'm making a workstation image to roll out to labs or if I'm doing something with virtual machines. Plus you said right in the question that you're hoping to change drive configurations and I've been there with some cloning; a slight change in drive geometry can result in major headaches with many cloning options. Many of the ones I've used do NOT like it when you change the underlying hardware in a cloned restore.
What you might want instead is to look into Amanda or Bacula, backup solutions that you can save your system to another media and restore parts as needed.
Alternatively, depending on how this server is used, we rolled out a VMWare ESXi system and put several servers on it. To do a poor man's cloning of a server we can (because of our environment; business production systems that are needed 24/7 wouldn't have this particular solution available) shut down the server and copy the hard drive image to another ESXi system or network storage system then start the VM back up. To "recover," we can put the drive images on another ESXi system and fire up the VM there. Slow compared to VMWare's pay-for options featuring livemotion and such but if you can afford the extra management and time overhead, it can work.
Alternatively in a VM environment you can just back up the the guest VM with regular Windows/Linux backup tools (so there's no need to take the VM offline) and if something goes wrong restore to another blank VM on another VM host as if it were a "clean" restore.
There are tools for doing a physical to virtual migration if you think this may be an option for your situation. From your description, though, cloning may not be the best option.
Another alternative would be to use utilities like tar or dump or even rsync to capture a snapshot of your filesystem to a network share or other media. You would have to examine your particular usage case, though, since some of these utilities don't like busy filesystems and/or open file handles.