Another way of doing it would be to use a PIC to store the current serial number in it's eeprom (that way it's not lost if you power it down).
Use a simple serial link from the 'new' pic that needs a number to the PIC with the serial number count.
The 'new' send a serial command to the master pic to request a number and the master sends the latest unique number. 'new' pic writes it to it's onboard eeprom and never asks for a new number upon boot.

It's similar to the way DHCP works on TCP/IP networking... Thats where i got the idea from...