HP recovery DVDs will be a good start. But ... if you ever have to use the disk(s) will your machine be restored to the original operating system or to the Ultimate now on it? If I buy a computer with Windows 7 Home Premium, and later upgrade to Windows 7 Ultimate, the recovery disks I get from the manufacturer will put Home Premium back on the machine.
Once you get the machine back, may I respectfully suggest you look into creating a system image on an external hard drive. Much better than recovery disks or recovery partitions. You'd set up your machine to your liking. Install programs, personalize settings, etc. When you create a system image it's like taking a "snapshot" of the entire hard drive. Everything is saved. If your computer becomes infected or a program causes the hard drive to crash, you can restore your machine with the system image and it will be exactly like it was when the image was created. The more often you create a system image the more current the computer will be. Just a thought.
Please post back with any other info the shop gives you.