I too had the same problem with a new HP laptop.
sda1 was a System partition
sda2 was Windows 7 partition
sda3 was a Recovery image partition
sda4 was the HP Tools partition
No room for another primary partition for Linux. My solution was to use the HP Tools utility to make a set of recovery DVD's, so then I no longer needed the Recovery image partition. First task, delete all the bloatware that just takes up disk space. Then I used the Windows 7 utilities to modify the disk partitions, first to delete the recovery partition (D

, then to defrag the entire disk, then to shrink the Windows partition. I started with a 500 GB drive, and was only able to shrink Windows down to 210, even though it was a brand new machine with nothing on it except what came from the factory, but this still left me 255 GB for the new Linux partition.
Then use the Linux installer (I used Mint 10) to create an extended partition in the new free space. I created a 6GB swap partiton and a 249 GB ext3 partition, and the install completed without any problems. Some people recommend a third (or more) extended partition for saving data to, so you may want to pursue that route, but it's not absolutely necessary. Depends upon your backup strategy, I suppose.
The machine dual boots now, but I can't remember the last time I booted into Windows. This is my first Linux machine and I love it. Don't miss Windows at all, except that Netflix won't stream to a Linux OS. Other than that, it does everything as well or better than I was used to doing in Windows.