I suggest going onto one of the 16 bit processors.
They have a real time clock module, a couple of serial ports, and loads of memory for storing lots of readings. You can write to the program space if you want it non-volatile, but a small battery will keep it going for ages if you go to sleep or a low power mode.
I have run 3 of the DS18B20s on one pin of the pic24FJ series pics. I can post the code tomorrow if anyone wants it. The program got all of the DS18B20s to convert the temperatures at the same time, then read them individually.
It is possible to make a program work out the serial numbers of all the DS18B20s on one wire. However, you then have the problem of working out which serial number is which sensor. On my application, the sensors are all on one water tank so the highest temperature is the physically highest.
If you need to work out which is which, you can wire to separate pins on the pic, or you can write code that displays the serial number and connect one DS18B20 at a time. Alternatively, you can heat each sensor in turn and see which result goes up.