Have you checked the memory slots for dirt and made sure the SIMM itself is clean?
There's also the risk, albeit very small, that removing/reinserting the memory has damaged the contacts between the socket/pcb. A single cracked solder joint is all it takes for random behaviour like this.
You also need to try other memory modules if you have any spare. I always keep a few old 16MB modules lying around for times like this.
