My first suggestion would be (and I'm just guessing here since you said nothing about it in your posting) to add a reset supervisor circuit. I'm guessing that you don't have one, that you're probably using that "single capacitor and internal resistor" setup. If you're already using a reset supervisor, well, then we go back to the drawing board.