Pardon the brief answer here, I just wanted to say that I have just added a extended partition to my HP g7-1150us that had 4 primary partitions as others have described, without losing anything. Here is how:
Since the laptop is limited to 100Mbps network connection, I took the 640GB HD out of the laptop and connected to a SATA port on my linux PC for the process. You could just use the network connection and boot linux from CD on the laptop instead.
First, I made a full backup image file of the laptop HD using the dd command.
Then using gparted I shrank the windows OS partition to make room for the new extended partition I want to install.
Then I made image files of the individual partitions and the MBR also using dd. I noted the start sector positions of each partition as indicated in gparted.
Then using gparted, I deleted the small HP_TOOLS partition from the laptop HD.
Then I created an extended partition using all of the free space with gparted.
Then I moved the RESTORE partition into the extended partition as a new logical partition all the way to the right within the extended partition using gparted again.
Then I resized the extended partition until the starting sector of the RESTORE logical position was the same as before. I am not sure if this was required or not.
Then I created a fat32 primary partition at the same starting sector that the HP_TOOLS partition was at before I deleted it, using gparted. Again I am not sure if lining up the starting sector is required for this to work.
Then I used dd to copy the HP_TOOLS backup image into the newly created fat32 partition.
I put the HD back into the laptop, checking windows boot, tools boot (F2) and restore boot (F11). They all worked just fine. No need for USB or permanently deleting potentially useful factory installed partitions.
To summarize, I just moved the RESTORE partition into a new extended partition and everything works.
What remains to be seen, is how GRUB will work with all of this after I install Linux within the extended partition. I am almost certain that the HP_TOOLS and RESTORE functions will stop working, but at least they are on the disk if needed. Additionally, in a serious crisis, I have a full image of the factory HD. Gparted and dd are excellent free tools to use for all of this.
UPDATE: Using a graphical Windows BCDeditor from neosmart.net I made Windows in control of the option to boot Linux. When I installed Ubuntu 12.04 from a USB drive (I used unetbootin to create the USB image from the 12.04 ISO image) I am now able to boot Windows, use F2 for tools, use F11 for restore and boot into Ubuntu. So if anyone was wondering, yes, it is possible to install Linux alongside Windows 7 on a HP laptop that was factory installed with 4 primary partitions, without losing any of the factory functionality and without having to burn DVD's and without having to keep a USB drive around for emergencies.
Happy hacking and cheers!