Thanks Peter,
I also cloned from optiboot. So I tried again from scratch using just the terminal code you mentioned, but still the same; hunk 4 fails.
kx@kx-laptop:~/Programming/Arduino/arduino-1.0.1/hardware/sanguino164p/bootloaders$ hg clone https://code.google.com/p/optiboot/
destination directory: optiboot
requesting all changes
adding changesets
adding manifests
adding file changes
added 34 changesets with 299 changes to 119 files
updating to branch default
36 files updated, 0 files merged, 0 files removed, 0 files unresolved
kx@kx-laptop:~/Programming/Arduino/arduino-1.0.1/hardware/sanguino164p/bootloaders$ cd optiboot
kx@kx-laptop:~/Programming/Arduino/arduino-1.0.1/hardware/sanguino164p/bootloaders/optiboot$ patch -p1 < patch.txt
patching file optiboot/bootloaders/optiboot/Makefile
patching file optiboot/bootloaders/optiboot/makeall
patching file optiboot/bootloaders/optiboot/optiboot.c
patching file optiboot/bootloaders/optiboot/pin_defs.h
Hunk #1 FAILED at 44.
1 out of 1 hunk FAILED -- saving rejects to file optiboot/bootloaders/optiboot/pin_defs.h.rej
If I apply the last hunk manually and proceed, ( that is, in pin_defs.h
replace #if defined(AVR_ATmega644P) || defined(AVR_ATmega1284P) with #if defined(AVR_ATmega164P) || defined(AVR_ATmega644P) || defined(AVR_ATmega1284P) )
and ./makeall, I get
kx@kx-laptop:~/Programming/Arduino/arduino-1.0.1/hardware/sanguino164p/bootloaders/optiboot/optiboot/bootloaders/optiboot$ ./makeall
rm -rf *.o *.elf *.lst *.map *.sym *.lss *.eep *.srec *.bin *.hex
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega8 -DF_CPU=16000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -c -o optiboot.o optiboot.c
optiboot.c:319:0: warning: "RAMSTART" redefined
/usr/lib/gcc/avr/4.5.3/../../../avr/include/avr/iom8.h:568:0: note: this is the location of the previous definition
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega8 -DF_CPU=16000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -Wl,--section-start=.text=0x1e00 -Wl,--section-start=.version=0x1ffe -Wl,--relax -Wl,--gc-sections -nostartfiles -nostdlib -o optiboot_atmega8.elf optiboot.o
avr-size optiboot_atmega8.elf
text data bss dec hex filename
488 0 0 488 1e8 optiboot_atmega8.elf
/// ............Cut a section out because of character limit in this forum ...............//////
506 0 0 506 1fa optiboot_pro_16MHz.elf
avr-objcopy -j .text -j .data -j .version --set-section-flags .version=alloc,load -O ihex optiboot_pro_16MHz.elf optiboot_pro_16MHz.hex
avr-objdump -h -S optiboot_pro_16MHz.elf > optiboot_pro_16MHz.lst
rm optiboot.o optiboot_pro_16MHz.elf
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega168 -DF_CPU=20000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -c -o optiboot.o optiboot.c
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega168 -DF_CPU=20000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -Wl,--section-start=.text=0x3e00 -Wl,--section-start=.version=0x3ffe -Wl,--relax -Wl,--gc-sections -nostartfiles -nostdlib -o optiboot_pro_20mhz.elf optiboot.o
avr-size optiboot_pro_20mhz.elf
text data bss dec hex filename
506 0 0 506 1fa optiboot_pro_20mhz.elf
avr-objcopy -j .text -j .data -j .version --set-section-flags .version=alloc,load -O ihex optiboot_pro_20mhz.elf optiboot_pro_20mhz.hex
avr-objdump -h -S optiboot_pro_20mhz.elf > optiboot_pro_20mhz.lst
rm optiboot.o optiboot_pro_20mhz.elf
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega328p -DF_CPU=8000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -c -o optiboot.o optiboot.c
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega328p -DF_CPU=8000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -Wl,--section-start=.text=0x7e00 -Wl,--section-start=.version=0x7ffe -Wl,--relax -Wl,--gc-sections -nostartfiles -nostdlib -o optiboot_atmega328_pro_8MHz.elf optiboot.o
avr-size optiboot_atmega328_pro_8MHz.elf
text data bss dec hex filename
506 0 0 506 1fa optiboot_atmega328_pro_8MHz.elf
avr-objcopy -j .text -j .data -j .version --set-section-flags .version=alloc,load -O ihex optiboot_atmega328_pro_8MHz.elf optiboot_atmega328_pro_8MHz.hex
avr-objdump -h -S optiboot_atmega328_pro_8MHz.elf > optiboot_atmega328_pro_8MHz.lst
rm optiboot.o optiboot_atmega328_pro_8MHz.elf
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega644p -DF_CPU=16000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' '-DBIGBOOT' -c -o optiboot.o optiboot.c
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega644p -DF_CPU=16000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' '-DBIGBOOT' -Wl,--section-start=.text=0xfc00 -Wl,--section-start=.version=0xfffe -Wl,--relax -Wl,--gc-sections -nostartfiles -nostdlib -o optiboot_atmega644p.elf optiboot.o
avr-size optiboot_atmega644p.elf
text data bss dec hex filename
506 0 0 506 1fa optiboot_atmega644p.elf
avr-objcopy -j .text -j .data -j .version --set-section-flags .version=alloc,load -O ihex optiboot_atmega644p.elf optiboot_atmega644p.hex
avr-objdump -h -S optiboot_atmega644p.elf > optiboot_atmega644p.lst
rm optiboot.o optiboot_atmega644p.elf
make: *** No rule to make target `mega'. Stop.
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega88 -DF_CPU=16000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -c -o optiboot.o optiboot.c
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=atmega88 -DF_CPU=16000000L '-DLED_START_FLASHES=3' '-DBAUD_RATE=115200' -Wl,--section-start=.text=0x1e00 -Wl,--section-start=.version=0x1ffe -Wl,--relax -Wl,--gc-sections -nostartfiles -nostdlib -o optiboot_atmega88.elf optiboot.o
avr-size optiboot_atmega88.elf
text data bss dec hex filename
506 0 0 506 1fa optiboot_atmega88.elf
avr-objcopy -j .text -j .data -j .version --set-section-flags .version=alloc,load -O ihex optiboot_atmega88.elf optiboot_atmega88.hex
avr-objdump -h -S optiboot_atmega88.elf > optiboot_atmega88.lst
rm optiboot.o optiboot_atmega88.elf
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=attiny84 -DF_CPU=1000000L '-DLED_START_FLASHES=3' '-DSOFT_UART' '-DBAUD_RATE=9600' '-DVIRTUAL_BOOT_PARTITION' -c -o optiboot.o optiboot.c
optiboot.c:313:0: warning: "RAMSTART" redefined
/usr/lib/gcc/avr/4.5.3/../../../avr/include/avr/iotn84.h:42:0: note: this is the location of the previous definition
avr-gcc -g -Wall -Os -fno-inline-small-functions -fno-split-wide-types -mshort-calls -mmcu=attiny84 -DF_CPU=1000000L '-DLED_START_FLASHES=3' '-DSOFT_UART' '-DBAUD_RATE=9600' '-DVIRTUAL_BOOT_PARTITION' -Wl,--section-start=.text=0x1d00 -Wl,--section-start=.version=0x1efe -Wl,--relax -Wl,--gc-sections -nostartfiles -nostdlib -o optiboot_luminet.elf optiboot.o
avr-size optiboot_luminet.elf
text data bss dec hex filename
602 0 0 602 25a optiboot_luminet.elf
avr-objcopy -j .text -j .data -j .version --set-section-flags .version=alloc,load -O ihex optiboot_luminet.elf optiboot_luminet.hex
avr-objdump -h -S optiboot_luminet.elf > optiboot_luminet.lst
rm optiboot.o optiboot_luminet.elfIs this expected? Should I have also gotten an atmega164 hex, or is the 644 hex now suitable to be renamed and tried with the 164 chip?
Also, about the price, I'm just talking about my local electronics shop here in Tokyo where the 1284s are 600yen, and the 164s are 300yen (6 Euro / 3 Euro), and the 1284s and 644s are constantly out of stock, whereas they always have plenty of 164s 
Thanks again