The immortality part is uncertain: in canon it let Flamel survive for six centuries, but in HPMOR Quirrel claims that the stone's current holder is not the one who made it.)

In canon, the elixir of youth is something you have to make and drink over and over; if the Stone were stolen, and you were unable to make a replacement in time, you would die of old age. It's possible that this is what happened, with Flamel as the thief. This would also explain why he can't make more Stones.