MacOS – How to update Time Machine’s recovery partition

First, open a Terminal.

Status before:

$ diskutil list
/dev/disk0
  #:                       TYPE NAME                    SIZE       IDENTIFIER
  0:      GUID_partition_scheme                        *128.0 GB   disk0
  1:                        EFI                         209.7 MB   disk0s1
  2:                  Apple_HFS Macintosh HD            127.8 GB   disk0s2

Get Lion Recovery Update v1.0 (431.91 MB)

Mount RecoveryHDUpdate.dmg

$ hdiutil attach ~/Downloads/RecoveryHDUpdate.dmg

Extract data from RecoveryHDUpdate.pkg

$ pkgutil --expand /Volumes/Mac\ OS\ X\ Lion\ Recovery\ HD\ Update/RecoveryHDUpdate.pkg ~/Desktop/RHD

Mount RecoveryHDMeta.dmg (in the RecoveryHDUpdate.pkg package)

$ hdiutil attach ~/Desktop/RHD/RecoveryHDUpdate.pkg/RecoveryHDMeta.dmg

Run tool that will finally resize current partition and create recovery

$ ~/Desktop/RHD/RecoveryHDUpdate.pkg/Scripts/Tools/dmtest ensureRecoveryPartition / /Volumes/Recovery\ HD\ Update/BaseSystem.dmg 0 0 /Volumes/Recovery\ HD\ Update/BaseSystem.chunklist
Creating recovery partition: finished

Status after:

$ diskutil list
/dev/disk0
  #:                       TYPE NAME                    SIZE       IDENTIFIER
  0:      GUID_partition_scheme                        *128.0 GB   disk0
  1:                        EFI                         209.7 MB   disk0s1
  2:                  Apple_HFS Macintosh HD            127.2 GB   disk0s2
  3:                 Apple_Boot Recovery HD             650.0 MB   disk0s3

My suggestion

Don't try to resize from the Recovery partition. Boot into the normal partition and resize from there.

Background

diskutil list is misleading you. It is not the position of the recovery partition which is your problem.

I had a very similar setup, and here is the output of diskutil list for me:

  #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:      GUID_partition_scheme                        *500.1 GB   disk0
   1:                        EFI                         209.7 MB   disk0s1
   2:                  Apple_HFS Macintosh HD            423.6 GB   disk0s2
   3:                 Apple_Boot Recovery HD             650.0 MB   disk0s3
   4:                  Apple_HFS Temp Partition Test ... 74.8 GB    disk0s4
   5:                 Apple_Boot Recovery HD             792.2 MB   disk0s5

Partitions 4 and 5 had a dev version of Lion on them. I have just used Disk utility to delete partitions 4 and 5 and resize partition 2 to fill the space.

This worked - Disk Utility resized the main drive with no problem. So what have I done which is different to you? Well, I resized the main partition from booting into the main partition not the Recovery Partiion. You can resize a partition that you have booted from in Disk Utility.

It makes sense that the recovery partition would "get in the way" if you have booted from it, so I suspect that above suggestion might work for you.